python - 在 Python 列表中存储大量数据

Question

我想要一个程序生成最多 10^9 的素数。 我正在使用埃拉托色尼筛法在 python 中实现它，但是当我尝试 10^9 时出现内存错误。它工作正常，直到 10^7。 这是我正在使用的代码

def prime(n):
    p=[True]*(n+1)
    p[0]=p[1]=False

    for i in range(int(n**0.5)+1):
        if p[i]:
            for j in range(i*i, n+1, i):
                p[j] = False

    for i in range(n+1):
        if p[i]:
            yield i

我使用的是 6GB RAM 的 Windows 10

Answer 1

您可以通过仅存储质数本身来获得巨大的加速，而不是在每个特定质数上存储 true 或 false。这将极大地简化您的程序，并且还应该允许您处理明显更大的值。

替代方法

尝试编译一个素数列表，然后仅测试这些素数以查看我们是否有任何除数。这要快得多，我这里没有内存问题，我尝试了 prime(655360002)(我在维基百科上查找)没有问题。

def prime(n):

    found_primes = []
    for number in range(2, int(n**0.5)+1):

        number_is_prime = True

        # The new number can only be divisible by other primes
        for divisor in found_primes:
            if number % divisor == 0:
                number_is_prime = False
                break

        if number_is_prime:
            found_primes.append(number)


    # Now that we have a list of primes, we test our number against them
    for prime in found_primes:
        if n % prime == 0:
            return False


    # IF we tried all primes, then we must be prime
    return True