use*_*445 14 algorithm numbers number-theory
什么是最有效的算法,任何人都可以想到,给定一个自然数n,返回最小自然数x与n个正除数(包括1和x)？例如,给定4算法应该得到6(除数:1,2,3,6); 即6是具有4个不同因子的最小数字.同样,给定6,算法应该得到12(除数:1,2,3,4,6,12); 即12是具有6个不同因子的最小数字
就真实世界的性能而言,我正在寻找一种可扩展的算法,它可以在一台可以每秒进行10 7次计算的机器上在2秒内给出10 20的答案.
alf*_*alf 12
http://www.primepuzzles.net/problems/prob_019.htm
b)Jud McCranie,TWA Baumann和Enoch Haga基本上发送相同的程序来找到给定d的N(d):
- 将d分解为其素数除数的乘积:d = p 1 a 1*p 2 a 2*p 3 a 3*...
- 将这个因子分解转换为另一个算术等效因子分解,由无动力单调递减和非必要因素组成......(uf!...)d = p 1 a 1*p 2 a 2*p 3 a 3*.. .= b 1*b 2*b 3 ......这样b 1 ≥b 2 ≥b 3 ...
你必须意识到,对于每一个给定d,还有可以做一些算术等价的因式分解:举例:
如果d = 16 = 2 4那么有5个等价的因子分解: d = 2*2*2*2 = 4*2*2 = 4*4 = 8*2 = 16- 对于d的所有等效因子分解,N是计算2 b 1 -1*3 b 2 -1*5 b 3 -1*...的最小数.使用相同的例子:
N(16)=这些中的最小值{2*3*5*7,2 3*3*5,2 3*3 3 2 7*3,2 15 } = 2 3*3*5 = 120
更新:数字大约10 20,请注意Christian Bau在同一页面上引用的笔记.