遍历小于n的数字，确定每个数字的质因数分解。

Question

我想要遍历每个小于N的数字，并知道每个数字的质因数分解。我的问题是如何以最佳方式完成这个任务？

我知道可以使用试除法来找到给定数字的质因数分解，并将其重复用于小于N的每个数字，但这很低效且比从已知质因数生成每个小于N的数字更耗时。我已经编写了一个以下面的方式来生成所有小于N的数字，该数字由小于N的所有质因数生成。有没有更快的方法来做到这一点？我正在尝试利用这个事实，即我正在为所有小于N的数字执行此操作以节省计算时间，而不是进行试除法。

我要完成的目标： 我有一个算法，我想在小于N的每个数字上运行它。对于这个算法，我需要每个数字的质因数分解。我正在尝试在最短时间内获得每个数字的质因数分解。我实际上不需要存储质因数分解，我只需要在算法中使用它们。 （代码中的solve(curNum, curFactors)函数是我的算法）

我编写了一个python3程序，使用递归方式生成每个数字并知道它的质因数，但速度非常慢。（当N = 10 ^ 7时，处理时间约为58秒。函数solve在此基准测试中未执行任何操作。）

curFactors是一个列表，其中每个偶数元素是因式分解中质数的索引，每个奇数元素是该质数的指数。我将其从列表的列表展平以节省计算时间。prime start index用于确保我不重复计算数字。目前，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://dev59.com/snI95IYBdhLWcg3w-DH0
primelist = primesfrom2to(upperbound+1)
lenPrimes = len(primelist)

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

有没有人知道更好的方法来做这件事？

- Ninja_Coder

---

你能否提供一个更清晰的解释，说明你想要实现什么？你想生成一个整数列表的列表，其中包含该列表索引值的质因数分解，直到某个限制为止？ - Sean Pianka

非常抱歉表述不够清晰。我有一个算法，想要在小于N的每个数字上运行。为了这个算法，我需要每个数字的质因数分解。我的问题是，获取每个小于N的数字的质因数分解的最快方法是什么。实际上，我并不需要将质因数分解存储在内存中，我只需要用质因数分解来运行算法即可。 - Ninja_Coder

Python Finding Prime Factors 和 Prime factorization - list - Sean Pianka

不，我不在乎，顺序无关紧要！ - Ninja_Coder

通常的非高级答案是使用最小质因数筛法，直到您的上限N的平方根，然后通过重复（非试验）除法和最小因子查找来使用它来找到每个数字的质因数分解，直到N。 - Will Ness

Answer 1

如果你已经实现了埃拉托色尼筛法并且其性能可接受，那么你可以修改它来存储质因数。

基本方法是这样的：每当你要“划掉”一个数或将它从列表中移除，因为它是某个质数的倍数时，改为检查你可以用该质数将它除尽多少次（使用/和%）。这将给你一个表示质因数分解组成部分的（质数，指数）对。在与原始数字相关联的列表或字典中存储这些对。当筛法完成时，每个列表都描述了相应数字的质因数分解。

- hnau

---

我的错误，感谢指出。我已经编辑了答案以进行更正。我认为我描述的方法需要粗心的N log N实现。 - hnau

在筛法的内部循环中，不需要分割，可以迭代两个变量。一个变量以质数为增量递增，另一个变量以1为增量递增。 - Yann Vernier

Answer 2

如果你想要一点乐趣，你可以使用Bach's algorithm在O(log(N))时间内生成介于[1,N]之间的随机数。重复此过程直到找到所有小于N的数字的质因数分解可能需要理论上的无限时间，但该算法的预期运行时间将是O(Nlog(N))。

这可能会有一些效率上的损失，但如果你想要一个不按线性顺序迭代的有趣算法，那么这可能是你最好的选择 :)

- Milo Moses

Answer 3

使用欧拉筛法的灵感，您可以通过将质数传播到N的质因数列表中来构建因子列表：

仅需知道哪些素数存在：

def primeFactors(N):
    result = [[] for _ in range(N+1)]  # lists of factors from 0..N
    for p in range(1,N+1,2):
        if p<2: p=2 
        if result[p]: continue         # empty list is a prime 
        for k in range(p,len(result),p):
                result[k].append(p)    # propagate it to all multiples
    return result

print(*enumerate(primeFactors(10)))
# (0, []) (1, []) (2, [2]) (3, [3]) (4, [2]) (5, [5]) (6, [2, 3]) (7, [7]) (8, [2]) (9, [3]) (10, [2, 5])

获取每个质数在因式分解中的所有实例：

def primeFactorsAll(N):
    result = [[] for _ in range(N+1)]
    for p in range(1,N+1,2):
        if p<2: p=2
        if result[p]: continue
        pn = p
        while pn < N:
            for k in range(pn,len(result),pn): # propagate to multiples of
                result[k].append(p)            # each power of p
            pn *= p
    return result

print(*enumerate(primeFactorsAll(10)))
# (0, []) (1, []) (2, [2]) (3, [3]) (4, [2, 2]) (5, [5]) (6, [2, 3]) (7, [7]) (8, [2, 2, 2]) (9, [3, 3]) (10, [2, 5])

对于较大的N，这种方法应该比除法方法运行得更快。 在我的笔记本电脑上，当N=10^7时，primeFactors(N)花费了8.1秒，而primeFactorsAll(N)花费了9.7秒。

- Alain T.