来自 欧拉计划500题
120的因子数量是16。事实上，120是具有16个因子的最小数。
找到2**500500个因子的最小数字。将答案对500500507取模。
计算n的因子很简单，例如在Python中len([i for i in range(1,n+1) if n % i == 0])。时间复杂度为O(n)。
我尝试了暴力搜索，并发现具有32个因子的最小数字是840，但它对于以上问题来说太慢了。根据不等式count_divisors(n) <= n，这个数字将会非常大。
您怎么看？有什么想法吗？如何计算具有某些因子数量的最小数？
编辑：我不认为这是重复的。这个问题更加具体，它涉及到一类更大的数字。其他问题是一般性的。它的答案不适用于这个问题，因为它是一个不同的数量级。
n的因子数量公式：
d(n) = (a1+1)(a2+1)...(ak+1)
其中
n = p1a1 * p2a2 *p3a3 *...*pkak
是每个整数通过其质因子的幂的唯一表示。这是一个众所周知的公式，但如果有人想知道如何获得它，那么请注意，如果且仅当d是形如p1x1 * p2x2 *p3x3 *...*pkxk的形式时，d才能被n整除，其中每个xi在0和ai之间，因此每个xi都有ai + 1种选择。现在只需应用乘法法则，您就可以得到所需的公式。d(n)（如您的情况），最小的n值显然是通过谨慎选择现有质数的幂或添加新质数来获得的。让我们通过这个简单的例子16来解释一下：x的最小值，增加2的幂（即增加a1）是否更好，还是使用7（即取a4=1而不是a4=0）？很容易检查，2*3*5*7 > 23 * 3 * 5 = 120，这就是本例中的答案。d(x)）的2的幂，因为您的最终目标是找到具有2500500个因子的最小数。堆初始化为前k个质数（在问题陈述中，k = 500500），并且在每个步骤中，当您从堆中Step Heap d(x) x
==========================
0 2,3,5,7 1 1
1 3,4,5,7 2 2
2 4,5,7,9 4 6
3 5,7,9,16 8 24
4 7,9,16,25 16 120
希望这有所帮助。
d(n) 问题的一半，我相信另一半在选择质数幂的实质中。 - Michael以下是我的Javascript代码的高级概述 - 其中factorCount表示因子数量：
factorCountfactorCount个因子的最小数字以下是我的JavaScript函数的高级代码分解：
var primeFactors = findPrimeFactors(factorCount);
var primeFactorCombinations = removeDuplicateArrays(generateCombinations(primeFactors, 1));
var combinedFactorCandidates = generateCombinedFactorCombinations(primeFactors, primeFactorCombinations);
var smallestNumberWithFactorCount = determineMinimumCobination(combinedFactorCandidates);
以下是完整的sha-bang：
function smallestNumberByFactorCount(factorCount) {
function isPrime(primeCandidate) {
var p = 2;
var top = Math.floor(Math.sqrt(primeCandidate));
while(p<=top){
if(primeCandidate%p === 0){ return false; }
p++;
}
return true;
}
function findPrimeAfter(currentPrime) {
var nextPrimeCandidate = currentPrime + 1
while(true) {
if(isPrime(nextPrimeCandidate)){
return nextPrimeCandidate;
} else {
nextPrimeCandidate++;
}
}
}
function findPrimeFactors(factorParent) {
var primeFactors = [];
var primeFactorCandidate = 2;
while(factorParent !== 1){
while(factorParent % primeFactorCandidate === 0 && factorParent !== 1 ){
primeFactors.push(primeFactorCandidate);
factorParent /= primeFactorCandidate;
}
primeFactorCandidate = findPrimeAfter(primeFactorCandidate);
}
return primeFactors;
}
function sortArrayByValue(a,b){
return a-b;
}
function clone3DArray(arrayOfArrays) {
var cloneArray = arrayOfArrays.map(function(arr) {
return arr.slice();
});
return cloneArray;
}
function doesArrayOfArraysContainArray(arrayOfArrays, array){
var aOA = clone3DArray(arrayOfArrays);
var a = array.slice(0);
for(let i=0; i<aOA.length; i++){
if(aOA[i].sort().join(',') === a.sort().join(',')){
return true;
}
}
return false;
}
function removeDuplicateArrays(combinations) {
var uniqueCombinations = []
for(let c=0; c<combinations.length; c++){
if(!doesArrayOfArraysContainArray(uniqueCombinations, combinations[c])){
uniqueCombinations[uniqueCombinations.length] = combinations[c];
}
}
return uniqueCombinations;
}
function generateCombinations(parentArray, minComboLength) {
var generate = function(n, src, got, combinations) {
if(n === 0){
if(got.length > 0){
combinations[combinations.length] = got;
}
return;
}
for (let j=0; j<src.length; j++){
generate(n - 1, src.slice(j + 1), got.concat([src[j]]), combinations);
}
return;
}
var combinations = [];
for(let i=minComboLength; i<parentArray.length; i++){
generate(i, parentArray, [], combinations);
}
combinations.push(parentArray);
return combinations;
}
function generateCombinedFactorCombinations(primeFactors, primeFactorCombinations) {
var candidates = [];
for(let p=0; p<primeFactorCombinations.length; p++){
var product = 1;
var primeFactorsCopy = primeFactors.slice(0);
for(let q=0; q<primeFactorCombinations[p].length; q++){
product *= primeFactorCombinations[p][q];
primeFactorsCopy.splice(primeFactorsCopy.indexOf(primeFactorCombinations[p][q]), 1);
}
primeFactorsCopy.push(product);
candidates[candidates.length] = primeFactorsCopy.sort(sortArrayByValue).reverse();
}
return candidates;
}
function determineMinimumCobination (candidates){
var minimumValue = Infinity;
var bestFactorCadidate = []
for(let y=0; y<candidates.length; y++){
var currentValue = 1;
var currentPrime = 2;
for(let z=0; z<combinedFactorCandidates[y].length; z++){
currentValue *= Math.pow(currentPrime,(combinedFactorCandidates[y][z])-1);
currentPrime = findPrimeAfter(currentPrime);
}
if(currentValue < minimumValue){
minimumValue = currentValue;
bestFactorCadidate = combinedFactorCandidates[y];
}
}
return minimumValue;
}
var primeFactors = findPrimeFactors(factorCount);
var primeFactorCombinations = removeDuplicateArrays(generateCombinations(primeFactors, 1));
var combinedFactorCandidates = generateCombinedFactorCombinations(primeFactors, primeFactorCombinations);
var smallestNumberWithFactorCount = determineMinimumCobination(combinedFactorCandidates);
return smallestNumberWithFactorCount;
}
> smallestNumberByFactorCount(3) --> 4
> smallestNumberByFactorCount(4) --> 6
> smallestNumberByFactorCount(5) --> 16
> smallestNumberByFactorCount(6) --> 12
> smallestNumberByFactorCount(16) --> 120
> smallestNumberByFactorCount(100) --> 45360
> smallestNumberByFactorCount(500) --> 62370000
> smallestNumberByFactorCount(5000) --> 4727833110000
> smallestNumberByFactorCount(100000000) --> 1.795646397225103e+40
不是完整的答案，而是一些提示：
n的最大整数因子是n/2
所以不需要检查所有小于n的因子
可以使用质因数分解
最大的质因子是sqrt(n)，所以不需要测试到n，而是测试到sqrt(n)或者测试到具有n位一半的数字
m=(2^(ceil(ceil(log2(n))/2)+1))-1
这应该会加速一些事情，但您需要添加非质数因子的计算
这看起来像某种系列（质因数分解）
divisors | prime_divisors | non_prime_divisors | LCM(all divisors)
1 | 1 | | 1
2 | 1,2 | | 2
3 | 1,2 | 4 | 4
4 | 1,2,3 | 6 | 6
5 | 1,2 | 4,8,16 | 16
6 | 1,2,3 | 4,6,12 | 12
7 | 1,2 | 4,8,16,32,64 | 64
8 | 1,2,3 | 4,6,8,12,24 | 24
...
16 | 1,2,3,5 |4,6,8,10,12,15,20,24,30,40,60,120 | 120
因此，尝试找到生成此顺序的方程式，然后在模算术中简单计算第n个迭代（简单的PI操作... modmul）。我可以看到偶数和奇数元素有不同的方程...
[编辑1] 分解到16个因子
1: 1
2: 1, 2
3: 1, 2, 4
4: 1, 2, 3, 6
5: 1, 2, 4, 8, 16
6: 1, 2, 3, 4, 6, 12
7: 1, 2, 4, 8, 16, 32, 64
8: 1, 2, 3, 4, 6, 8, 12, 24
9: 1, 2, 3, 4, 6, 9, 12, 18, 36
10: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
11: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,1024
12: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
13: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,1024,2048,4096
14: 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 192
15: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144
16: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120
sqrt(n) 或 p*p 测试更少的比特数... - Spektre最小整数2**500,500的质因数分解（PF）的缩写形式如下：
2**31 * (3...7)**15 * (11...47)**7 * (53...2,713)**3 * (2,719...7,370,029)
具有2^n个因子的最小正整数是前n个质数和质数幂的乘积。质数幂(pp)是质数的2^(2^e)次方（幂为2、4、8、16...）。前3个pp是4、9和16（2^2、3^2和2^4）。
由于PF中仅使用质因数，因此您会注意到pp与质因数聚合在一起。对于n = 500,550，以下是一些统计数据或计数： PF中的5个术语（幂为31、15、7、3、1）。 总质数(P) = 500,084 质数幂(pp) = 416 总P + pp = n = 500,500 请参见上面的定理。
Single primes (the last term of the PF) total 499,688.
你可以使用Sage Math和Excel（不过在Excel中需要一个素数计数函数）来计算这个PF（以及其他2^n的值）。
此外，你应该检查你的PF解决方案。可以通过为各种pp和单个质数分配权重来检查原始n来完成这个任务。
def findfactors(num):
list1=[]
for i in range(num,1,-1):
if num%i==0:
list1.append(i)
return list1
def getcombinations(num):
factors=findfactors(num)
list1=[]
if num==1:
return 1
for i in factors:
if getcombinations(num//i)!=1:
list1.append([i,getcombinations(num//i)])
else:
list1.append(i)
return list1
def unloadlist(list1):
list2=[]
if type(list1).__name__=="list":
for i in list1[1]:
if type(i).__name__=="list":
i=unloadlist(i)
if type(i).__name__=="list":
flag=True
for j in i:
if type(j).__name__=="list":
list2.append([list1[0]]+j)
flag=False
if flag==True:
list2.append([list1[0]]+i)
else:
list2.append([list1[0],i])
if len(list2)==1:
list2=list2[0]
else:
list2=list1
return list2
def mergeitems(list1):
list2=[]
for i in list1:
if type(i).__name__=="int":
list2.append((i,))
elif type(i).__name__=="list":
if type(i[0]).__name__!="list":
list2.append(tuple(sorted(i,reverse=True)))
else:
for j in i:
list2.append(tuple(sorted(j,reverse=True)))
set1=set(list2)
return set1
def find_smallest_number(num):
#start writing your code here
list1=getcombinations(num)
for i in range(0,len(list1)):
list1[i]=unloadlist(list1[i])
mainlist=mergeitems(list1)
possibles=[]
primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227]
for i in mainlist:
num=1
for j in range(0,len(i)):
num*=primes[j]**(i[j] - 1)
possibles.append(num)
return min(possibles)
num=7
print("The number of divisors :",num)
result=find_smallest_number(num)
print("The smallest number having",num," divisors:",result)
list1、list2、i、num、set1、mainlist、possibles都有些含糊不清。getcombinations似乎是一个列表或者一个数字，但它与通常意义上的组合（例如https://docs.python.org/3.6/library/itertools.html#itertools.combinations）没有关系。这个程序运行速度够快吗？`findfactors`让我有些担心，但我无法判断。 - Teepeemm哎呀，我刚用Java解决了这个问题。我的“具有2^n除数的最小数字”最终被表示为质数及其幂次的映射。
这个谜题与优化同样重要：让你的代码工作，然后进行大量重构。测试到约2^30个除数是绝对值得的，因为在优化时会出现各种二阶错误。重复使用先前计算的结果，尽量不要排序任何东西，并尽快停止迭代（NavigableSet和LinkedHashMap非常有用）。我不会教奶奶如何高效地测试素性。
我一直使用Java long，但是在这种大小的数字中很容易在计算过程中超过Long.MAX_VALUE，请记住：（A^2 * B）% C =（A * ((A * B) % C)) % C。
希望所有这些都能激励你而不是泄露答案。继续加油！
除了自己以外，任何数字的最大约数是它的一半。例如，120的最大约数是60（除了它本身）。因此，您可以将范围从（n+1）减少到（n/2）。
此外，为了使一个数字具有m个约数，根据上述逻辑，该数字必须至少为((m-1)*2)（-1是因为第m个数字是它本身）。例如，具有4个约数的数字必须至少为6。因此，您对n的搜索现在具有更小的范围。
这两个方法将稍微减少运行时间。
import primesieve # pip install primesieve
import heapq
def solve(k, modulus=None):
"""Calculate the smallest number with 2**k divisors."""
n = 1
costs = primesieve.generate_n_primes(k) # more than necessary
for i in range(k):
cost = heapq.heappop(costs)
heapq.heappush(costs, cost**2)
n *= cost
if modulus:
n %= modulus
return n
assert solve(4) == 120
if __name__ == "__main__":
print(solve(500500, 500500507))
完全功能的代码。
def find_smallest_number(num):
number2=0
if(num%8==0):
number2=min(2**((num/4)-1)*3**1*5**1 , 2**((num//2)-1)*3**1)
elif(num%9==0):
number2=2**((num/9)-1)*3**2*5**2
elif(num%2==0 and num%3==0):
number2=2**((num/6)-1)*3**2*5**1
elif((num%4==0)):
number2=2**((num/4)-1)*3**1*5**1
elif(num%2==0):
number2=2**((num/2)-1)*3**1
else:
number2=2**(num-1)
return number2
num=32
print("The number of divisors :",num)
result=find_smallest_number(num)
print("The smallest number having",num," divisors:",result)
d0<d1，n=LCM(all divisors)的值不仅仅是增加的...例如，对于d=5的约数，最小的n=16，而对于d=6的约数，最小的n=12!!! - Spektre