寻找具有给定因子数的最小数的算法

Question

什么是任何人能想到的最有效的算法，给定一个自然数 n，返回 n 为正的最小自然数 x除数(包括 1 和 x)？例如，给定 4，算法应得出 6(除数:1,2,3,6)；即 6 是具有 4 个不同因子的最小数字。类似地，给定 6，算法的结果应该是 12(除数:1,2,3,4,6,12)；即 12 是具有 6 个不同因子的最小数字

就现实世界的性能而言，我正在寻找一种可扩展的算法，它可以在一台可以做 10^{7 的机器上在 2 秒内给出 1020 数量级的答案} 每秒计算。

Answer 1

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:

1. Factorize d as a product of his prime divisors: d = p₁^a₁ * p₂^a₂ *p₃^a₃ *...
2. convert this factorization in another arithmetically equivalent factorization, composed of non-powered monotonically decreasing and not necesarilly prime factors... (uf!...) d = p₁^a₁ * p₂^a₂ *p₃^a₃ *... = b₁ * b₂ * b₃... such that b₁ ≥ b₂ ≥ b₃...
   You must realize that for every given d, there are several arithmetically equivalent factorizations that can be done: by example:
   if d = 16 = 2⁴ then there are 5 equivalent factorizations: d = 2*2*2*2 = 4*2*2 = 4*4 = 8*2 = 16
3. N is the minimal number resulting of computing 2^b₁-1 * 3^b₂-1 * 5^b₃-1 * ... for all the equivalent factorizations of d. Working the same example:
   N(16) = the minimal of these {2 * 3 * 5 * 7, 2³ * 3 * 5, 2³ * 3³, 2⁷ * 3, 2¹⁵} = 2³ * 3 * 5 = 120

更新:数字在 10²⁰ 左右，请注意同一页上引用的 Christian Bau 的注释。