python - 遍历 < n 的数字，确定每个数字的质因数分解

Question

我想遍历每个 < N 的数字，并知道每个数字的质因数分解。我的问题是最好的方法是什么？

我知道我可以使用试除法找到给定数字的质因数分解，然后对每个小于 N 的数字重复该操作，但这样做效率低下，而且比从已知的主要因素。我在下面编写了一个实现，用于从所有小于 N 的质因数生成小于 N 的每个数字。有没有更快的方法来做到这一点？我试图利用这样一个事实，因为我对所有小于 N 的数字都这样做以节省计算时间，而不是尝试除法。

我要实现的目标: 我有一个算法，我想在每个小于 N 的数字上运行。对于这个算法，我需要每个数字的质因数分解。我想在最短的时间内得到每个数字的质因数分解。我实际上不需要存储质因数分解，我只需要使用质因数分解来运行我的算法。 (算法就是代码中的solve(curNum, curFactors))

我编写了一个 python3 程序来递归生成每个数字，并了解其质因数，但速度很慢。 (当 N = 10^7 时，处理时间约为 58 秒。函数 solve 对此基准测试没有任何作用。)

curFactors 是一个列表，其中每个偶数元素都是分解中素数的索引，每个奇数元素是该素数的指数。我从列表列表中将其展平以节省计算时间。 prime 起始索引用于确保我不会重复计算数字。目前 Solve 什么都不做，只是为了我可以对这个函数进行基准测试。

def iterateThroughNumbersKnowingFactors(curNumber, curFactors, primeStartIndex):
    #Generate next set of numbers
    #Handle multiplying by a prime already in the factorization seperately.
    for i in range(primeStartIndex+1,lenPrimes):
        newNum = curNumber * primelist[i]
        if(newNum > upperbound):
            break
        newFactors = curFactors[:]
        newFactors.append(i)
        newFactors.append(1)
        #Do something with this number and its factors
        solve(newNum, newFactors)
        #Go get more numbers
        iterateThroughNumbersKnowingFactors(newNum,newFactors,i)
    if(primeStartIndex > -1):
        newNum = curNumber * primelist[primeStartIndex]
        if(newNum > upperbound):
            return
        currentNumPrimes = len(curFactors)
        curFactors[currentNumPrimes-1] += 1
        #Do something with this number and its factors
        solve(newNum, curFactors)
        #Go get more numbers
        iterateThroughNumbersKnowingFactors(newNum,curFactors,primeStartIndex)

upperbound = 10**7

#https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n
primelist = primesfrom2to(upperbound+1)
lenPrimes = len(primelist)

t0 = time.clock()
iterateThroughNumbersKnowingFactors(1,[],-1)
print(str(time.clock() - t0) +" seconds process time")

有谁知道更好的方法吗？

Answer 1

如果您已经实现了 Eratosthenes 筛法并且其性能可以接受，那么您可以修改它以存储质因数。

基本方法是这样的:无论何时你要“划掉”一个数字或将它从列表中删除，因为它是质数的倍数，而是检查你可以将它除以质数多少次而没有余数(使用 / 和 %)。这将为您提供一个 (prime, exponent) 对，表示素数分解的那个分量。将这些对存储在与原始数字关联的列表或字典中。当 Sieve 完成时，每个列表将描述相应数字的质因数分解。