什么是最有效的算法，任何人都可以想到的是，给定一个自然数的 N 的，返回最少的自然数的 X 的用的 N 的正除数（包括1和的 X 的）？例如，给定4的算法应该产生6（除数：1,2,3,6）; IE 6是具有4个不同的因素最小的数字。同样地，给定图6中，算法应该产生12（除数：1,2,3,4,6,12）;即12是具有最少数量6个不同的因素

在现实世界中的表现而言，我正在寻找一个可伸缩的算法，该算法可以提供10阶的答案 20 2秒的机器，可以做在10 7 每秒计算。

解决方案

http://www.primepuzzles.net/problems/prob_019.htm

  

二）士McCranie，T.W.A.鲍曼和放大器;诺哈加发送基本相同   方法找到的 N（D）的对于一个给定的 D：的

        比化的ð的是他的素因子的产物： D = P 1 在 1 * P 2 在 2 * P 3 在 3 * ... 的   在这转换分解在另一个算术相当于分解，无动力单调递减的，而不是由   necesarilly主要因素......（UF！...）的 D = P 1 在 1 * P 2 在 2 * P 3 在 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 的   的 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 ，注意票据由基督教巴乌引述同一页上

What's the most efficient algorithm anyone can think of that, given a natural number n, returns the least natural number x with n positive divisors (including 1 and x)? For example, given 4 the algorithm should result in 6 (divisors: 1,2,3,6); i.e. 6 is the smallest number having 4 distinct factors. Similarly, given 6, the algorithm should result in 12 (divisors: 1,2,3,4,6,12); i.e. 12 is the smallest number having 6 distinct factors

In terms of real-world performance, I'm looking for a scalable algorithm which can give answers of the order of 1020 within 2 seconds on a machine which can do 107 computations per second.

解决方案

http://www.primepuzzles.net/problems/prob_019.htm

b) Jud McCranie, T.W.A. Baumann & Enoch Haga sent basically the same procedure to find N(d) for a given d:

Factorize d as a product of his prime divisors: d = p1a1 * p2a2 *p3a3 *... convert this factorization in another arithmetically equivalent factorization, composed of non-powered monotonically decreasing and not necesarilly prime factors... (uf!...) d = p1a1 * p2a2 *p3a3 *... = b1 * b2 * b3... such that b1 ≥ b2 ≥ b3... You must realize that for every given d, there are several arithmetically equivalent factorizations that can be done: by example: if d = 16 = 24 then there are 5 equivalent factorizations: d = 2*2*2*2 = 4*2*2 = 4*4 = 8*2 = 16 N is the minimal number resulting of computing 2b1-1 * 3b2-1 * 5b3-1 * ... for all the equivalent factorizations of d. Working the same example: N(16) = the minimal of these {2 * 3 * 5 * 7, 23 * 3 * 5, 23 * 33, 27 * 3, 215} = 23 * 3 * 5 = 120

Update: With numbers around 1020, pay attention to the notes by Christian Bau quoted on the same page.