遍历包括素数在内的数字

Question

我想遍历从 1 到 n 的所有数字，我需要知道每个数字的素数因子。一个简单的实现是简单地遍历从 1 到 n 的所有数字并计算每个数字的质因数，花费 O(n^(3/2)).

的时间

我想出了这个解决方案，它只生成每个数字一次，并且每个素数额外生成一个数字（未生成），时间复杂度为 O(n + p)。

# primes contains enough primes so accessing it will never fail.
# Generate numbers 1 to limit (inclusive) including prime factors.
def gen(limit, i=0):
    # Primes above the limit are used 0 times, p**0 = 1
    if primes[i] > limit:
        yield 1, {}
        return

    # Generate all numbers using only higher primes...
    for n, f in gen(limit, i + 1):
        # ...and then add the current prime as often as possible each time.
        while n <= limit:
            yield n, f.copy()

            n *= primes[i]
            cf = f.get(primes[i], 0)
            f[primes[i]] = cf + 1

这会打印小限制的正确结果。然而，这个解决方案是递归的，并且很快达到最大堆栈大小。输出为

1 {}
2 {2: 1}
4 {2: 2}
8 {2: 3}
3 {3: 1}
6 {3: 1, 2: 1}
9 {3: 2}
5 {5: 1}
10 {5: 1, 2: 1}
7 {7: 1}

请注意，我不希望按顺序生成数字。

是否可以将其转化为迭代解决方案，或者是否有更简单的解决方案？

Answer 1

有一种使用记忆的更简单的方法。例如：

from functools import cache

@cache
def prime_factors(num):
    '''
    Example: 24 -> defaultdict({2: 3, 3: 1})
    '''
    assert isinstance(num, int) and num > 0

    # handle edge cases like 1
    if num == 1:
        return defaultdict(int)

    # find smallest divisor up to sqrt(num)
    # if no divisor found, num is prime
    # this can be optimized to only try prime divisors
    divisor, prime = 2, True
    while divisor**2 <= num:
        if num % divisor == 0:
            prime = False
            break
        divisor += 1

    if prime:
        factors = defaultdict(int)
        factors[num] += 1
    else:
        quotient = num // divisor
        # be sure to copy as dicts are mutable
        factors = prime_factors(quotient).copy()
        factors[divisor] += 1
    return factors

for i in range(10000):
    print(prime_factors(i))

这在技术上仍然是递归的，但在记忆的情况下，您只需进行查找。

遍历包括素数在内的数字

Iterating over numbers including prime factors

python

recursion

prime-factoring