当前位置：首页 → 问答吧 → 编程挑战题 - 最小合成数

编程挑战题 - 最小合成数

时间：2014-03-27

来源：互联网

其实之前汪汪都问过了(之前写FFT算法时需要用到)

见咁多人就问一条简单问题吧

如果给定一些质数, 例如2, 3, 5, 7
计算出大於或等於指定数字的最小合成数, 而合成数的质因数必须为上述指定的质数

input
n k: n为给定的质数个数, k为test case数目
并有以下条件:
1 <= n <= 10^3
1 <= k <= 10^3
[a ... z]: n个质数并有条件: 1 <= a <= 10^6
p: test case，条件: 10 <= p <= 10^12

input:
4 5
2 3 5 7
31
42
85
64
48
output:
32
42
90
64
48
解释:
32 = 2 ^ 5
42 = 2 * 3 * 7
90 = 2 * 3 ^ 2 * 5
64 = 2 ^ 6
48 = 2 ^ 4 * 3

[ 本帖最后由 Susan﹏汪汪於 2014-3-14 01:07 PM 使用编辑 ]

作者: Susan﹏汪汪发布时间: 2014-03-27

请加上数值范围：
a <= n <= b
每个测试案例数值 k，它的范围：
c <= k <= d

亦即请给出 a, b, c 及 d 的值。此等范围对选择算法有好大影响。

作者: fitcat07 发布时间: 2014-03-27

引用:原帖由 fitcat07 於 2014-3-14 12:16 PM 发表
请加上数值范围：
a

应该冇错了
第1000个质数系7927

[ 本帖最后由 Susan﹏汪汪於 2014-3-14 12:58 PM 使用编辑 ]

作者: Susan﹏汪汪发布时间: 2014-03-27

引用:原帖由 Susan﹏汪汪於 2014-3-14 12:20 PM 发表
应该冇错了
第1000个质数系7927

???

冇比 a - d 嘅数值喎...

作者: fitcat07 发布时间: 2014-03-28

引用:原帖由 fitcat07 於 2014-3-14 03:48 PM 发表
???

冇比 a - d 嘅数值喎...

有写、只是冇用字母代替

[ 本帖最后由 Susan﹏汪汪於 2014-3-14 03:56 PM 使用编辑 ]

作者: Susan﹏汪汪发布时间: 2014-03-28

有冇现成算法？
睇嚟好似得番暴力解一途...

作者: fitcat07 发布时间: 2014-03-28

引用:原帖由 fitcat07 於 2014-3-14 10:06 PM 发表
有冇现成算法？
睇嚟好似得番暴力解一途...

Search过好多次

就连关键字系咩都唔清楚

作者: Susan﹏汪汪发布时间: 2014-03-28

引用:原帖由 Susan﹏汪汪於 2014-3-13 11:35 PM 发表
其实之前汪汪都问过了(之前写FFT算法时需要用到)

见咁多人就问一条简单问题吧

如果给定一些质数, 例如2, 3, 5, 7
计算出大於或等於指定数字的最小合成数, 而合成数的质因数必须为上述指定的质数

input
n k: n为给 ...

有无时间限制?

可否放落二元树做 search，具体方法如下，如是 prime number 有 2 3 5 7, build the binary tree as below:

复制内容到剪贴板代码: 2
/ \
2 3
/ \ / \
2 3 3 5
/ \ / \ / \ / \
2 3 3 5 3 5 5 7
....

上面的 binary tree 简化了，应该系 level 1 是 2, level 2 是 2 * 2, 2 * 3, level 3 是 2 * 2 *2 ... 如此类推
直至左面最细数值的 node 的 value >= 最细 test case 的 value, 最右面的 node 的 value >= 最大 test case 的 value
然后对所有 test cases 做 binary search，找到就没有问题，找不到就 search 最接近的

作者: assembly.jc 发布时间: 2014-03-28

15呢

作者: Susan﹏汪汪发布时间: 2014-03-28

引用:原帖由 Susan﹏汪汪於 2014-3-14 10:17 PM 发表

Search过好多次

就连关键字系咩都唔清楚

我谂不如将呢题放入 SPOJ，等尐神人帮你做，你话好唔好？

作者: fitcat07 发布时间: 2014-03-28

引用:原帖由 fitcat07 於 2014-3-15 01:09 PM 发表
我谂不如将呢题放入 SPOJ，等尐神人帮你做，你话好唔好？

汪汪都唔识

作者: Susan﹏汪汪发布时间: 2014-03-28

唔识唔紧要喎，出题者唔一定要识㗎。

不过，如果要出，我谂要将范围定细一尐，等自己嘅程式都可以在限时内完成。并先放入 Tutorial，等待神人做完，作为参考。
然后，将神人写嘅程式，代入原本范围测试，再定下新嘅时间，放入 Classical，再等待更强嘅神人。

作者: fitcat07 发布时间: 2014-03-28

引用:原帖由 Susan﹏汪汪於 2014-3-15 12:57 PM 发表
15呢

Hi Susan,

对，这行不通

I have a question, Are there test cases that is not produced by given prime numbers? Say, given prime number, 2, 3, 5, 7, but the given the test case is 121 = 11 x 11?

作者: assembly.jc 发布时间: 2014-03-28

引用:原帖由 assembly.jc 於 2014-3-16 07:41 AM 发表

Hi Susan,

对，这行不通

I have a question, Are there test cases that is not produced by given prime numbers? Say, given prime number, 2, 3, 5, 7, but the given the test case is 121 = ...

如果test case出现121
输出125

作者: Susan﹏汪汪发布时间: 2014-03-28

放上 stackoverflow.com 度问，应该好快有人答。一试无妨。

作者: fitcat07 发布时间: 2014-03-28

引用:原帖由 fitcat07 於 2014-3-16 01:41 PM 发表
放上 stackoverflow.com 度问，应该好快有人答。一试无妨。

都好wor

作者: Susan﹏汪汪发布时间: 2014-03-28

引用:原帖由 Susan﹏汪汪於 2014-3-16 01:19 PM 发表

如果test case出现121
输出125

为何不是 122 呢?

作者: assembly.jc 发布时间: 2014-03-28

引用:原帖由 assembly.jc 於 2014-3-17 10:41 AM 发表

为何不是 122 呢?

122 = 2 * 61

作者: Susan﹏汪汪发布时间: 2014-03-28

实际应用真的有需要处理 10^12 咁大既 case???

引用:原帖由 Susan﹏汪汪於 2014-3-13 23:35 发表
其实之前汪汪都问过了(之前写FFT算法时需要用到)

见咁多人就问一条简单问题吧

如果给定一些质数, 例如2, 3, 5, 7
计算出大於或等於指定数字的最小合成数, 而合成数的质因数必须为上述指定的质数

input
n k: n为给 ...

作者: a8d7e8 发布时间: 2014-03-28

引用:原帖由 a8d7e8 於 2014-3-17 01:13 PM 发表
实际应用真的有需要处理 10^12 咁大既 case???

只系提升难度姐

作者: Susan﹏汪汪发布时间: 2014-03-28

更何况、处理64bit系统的话都要处理10^19的数字

作者: Susan﹏汪汪发布时间: 2014-03-28

我谂如果为咗加速 FFT, 咁不如在有可能应用到的范围内做 table 算咋..............

引用:原帖由 Susan﹏汪汪於 2014-3-17 13:22 发表

只系提升难度姐

作者: a8d7e8 发布时间: 2014-03-28

引用:原帖由 a8d7e8 於 2014-3-17 01:29 PM 发表
我谂如果为咗加速 FFT, 咁不如在有可能应用到的范围内做 table 算咋..............

就算系FFT
对於一个96000的data size（高标准音讯档的1秒）
都有可能处理超过192000长的data

作者: Susan﹏汪汪发布时间: 2014-03-28

对! data size 可能好大, 但系 arbitrary data size 有无需要准确到 1?

如果无, 可能有更有效方法做. 或者基本上大多数用 2^n 已经搅掂咁点解仲要搵最小合成数?

除非 - 你做紧一个 general real-time fft library....

引用:原帖由 Susan﹏汪汪於 2014-3-17 13:35 发表

就算系FFT
对於一个96000的data size（高标准音讯档的1秒）
都有可能处理超过192000长的data

作者: a8d7e8 发布时间: 2014-03-28

补充:

上例非 2^n

192000 / 5^3 = 1536
1536 / 2^9 = 3

多零尾用 5 除, 双数尾用 2 除, 剩返落嚟就算唔系 2,3,5,7 都可能可以用 table lookup 搵.

除非系质数, 或者大质数既合成数.

有几多资料会用呢啲长度呢?

引用:原帖由 a8d7e8 於 2014-3-17 14:28 发表
对! data size 可能好大, 但系 arbitrary data size 有无需要准确到 1?

如果无, 可能有更有效方法做. 或者基本上大多数用 2^n 已经搅掂咁点解仲要搵最小合成数?

除非 - 你做紧一个 general real-time fft libr ...

作者: a8d7e8 发布时间: 2014-03-28

引用:原帖由 a8d7e8 於 2014-3-17 02:28 PM 发表
对! data size 可能好大, 但系 arbitrary data size 有无需要准确到 1?

如果无, 可能有更有效方法做. 或者基本上大多数用 2^n 已经搅掂咁点解仲要搵最小合成数?

除非 - 你做紧一个 general real-time fft libr ...

汪汪的确写左general dimension general real-time fft library

作者: Susan﹏汪汪发布时间: 2014-03-28

引用:原帖由 a8d7e8 於 2014-3-17 02:32 PM 发表
补充:

上例非 2^n

192000 / 5^3 = 1536
1536 / 2^9 = 3

多零尾用 5 除, 双数尾用 2 除, 剩返落嚟就算唔系 2,3,5,7 都可能可以用 table lookup 搵.

除非系质数, 或者大质数既合成数.

有几多资料 ...

对一些通常输入的data size系可以任意长度（例如图片）
可能会有大质数的情况出现

作者: Susan﹏汪汪发布时间: 2014-03-28

http://www.fftw.org/

你个算法同佢比较边个快啲?

引用:原帖由 Susan﹏汪汪於 2014-3-17 14:38 发表

对一些通常输入的data size系可以任意长度（例如图片）
可能会有大质数的情况出现

作者: a8d7e8 发布时间: 2014-03-28

引用:原帖由 a8d7e8 於 2014-3-17 03:06 PM 发表
http://www.fftw.org/

你个算法同佢比较边个快啲?

佢冇实际的时间图

作者: Susan﹏汪汪发布时间: 2014-03-28

佢 claim "Arbitrary-size transforms (Sizes with small prime factors are best, but FFTW uses O(N log N) algorithms even for prime sizes)".见佢好耐之前做落啲 benchmark power of 2 同 intel ipp 有得 fight 或好接近. Non power of 2 快过 intel ipp.

引用:原帖由 Susan﹏汪汪於 2014-3-17 15:15 发表

佢冇实际的时间图

作者: a8d7e8 发布时间: 2014-03-28

引用:原帖由 a8d7e8 於 2014-3-17 03:22 PM 发表
佢 claim "Arbitrary-size transforms (Sizes with small prime factors are best, but FFTW uses O(N log N) algorithms even for prime sizes)".见佢好耐之前做落啲 benchmark power of 2 同 intel ipp 有得 ...

不过汪汪的FFT可以在合理时间内完成
至少在计算44100 size的data绝对不会超过1秒（即话可实时计算音乐的freq）
个library完全用c++ template写成而且唔大
所以汪汪还想移植到javascript

作者: Susan﹏汪汪发布时间: 2014-03-28

呢度提到用 sliding DFT O(n):
http://stackoverflow.com/questions/6663222/doing-fft-in-realtime

"It's based on the fact that once you have performed a fourier transform for the last N samples, and a new sample arrives, you can "undo" the effect of the oldest sample, and apply the effect of the latest sample, in a through the fourier data! This means that the sliding DFT performance is O(n)"

引用:原帖由 Susan﹏汪汪於 2014-3-17 15:32 发表

不过汪汪的FFT可以在合理时间内完成
至少在计算44100 size的data绝对不会超过1秒（即话可实时计算音乐的freq）
个library完全用c++ template写成而且唔大
所以汪汪还想移植到javascript

http://i.discuss.co ...

作者: a8d7e8 发布时间: 2014-03-28

引用:原帖由 a8d7e8 於 2014-3-17 03:55 PM 发表
呢度提到用 sliding DFT O(n):
http://stackoverflow.com/questions/6663222/doing-fft-in-realtime

"It's based on the fact that once you have performed a fourier transform for the last N samples, and a ...

佢果种系取巧的方法
在计算FFT时如果只是要求单点的freq
复杂度就是O(n)

作者: Susan﹏汪汪发布时间: 2014-03-28

我之后也在思考这个问题.......用逐个 sample 计算比较一 block sample 计算既 big-O 好似不太公平. 以及真正的应用会否每个 sample 也用 fft 去计..

真正应该会一 block block 咁计? 如果系咁就唔需要逐点 sample 计.

引用:原帖由 Susan﹏汪汪於 2014-3-17 18:17 发表

佢果种系取巧的方法
在计算FFT时如果只是要求单点的freq
复杂度就是O(n)

作者: a8d7e8 发布时间: 2014-03-28

引用:原帖由 a8d7e8 於 2014-3-17 06:26 PM 发表
我之后也在思考这个问题.......用逐个 sample 计算比较一 block sample 计算既 big-O 好似不太公平. 以及真正的应用会否每个 sample 也用 fft 去计..

真正应该会一 block block 咁计? 如果系咁就唔需要逐点 samp ...

显示就可以只要计算单点

但实际应用就一定要计晒全block data
因为例如做convolution、或者做声音的变频
都要为全部点的freq做操作

作者: Susan﹏汪汪发布时间: 2014-03-28