如何在 Python 中获得 2^63 - 1 内的素数集合

Question

我想在Python中得到一个2^63 - 1范围内的素数集合，在网上看到如下代码：

limit = 2**63 - 2
p = [True] * (limit + 1)
# p = bitarray(limit + 1)
p[0] = p[1] = False
for i in range(2, int(math.sqrt(limit) + 1)):
    if p[i]:
        for j in range(i * i, limit + 1, i):
            p[j] = False
prime = [i for i in range(limit + 1) if p[i]]
print(prime)

但是当我运行这个程序时，编译器抱怨can not fit 'int' into an index-sized integer。我尝试用bitarray来解决问题，但是array的index还是太大了

Answer 1

你可以使用 sympy:

import sympy

print(list(sympy.primerange(0,2**63-1)))

但是 2^63 很大，这需要一些时间。

Answer 2

如果您有某种 primes() 生成器，您可以这样做：

is_prime_var = 0

MAX = 1 << 5
last_p = 0
for p in primes():
    if p > MAX:
        break
    print(p, p-last_p)
    is_prime_var <<= (p - last_p)
    is_prime_var |= 1
    last_p = p
is_prime_var <<= (MAX - last_p - 1)

现在素数的位置存储在整数 is_prime_var 中（以相反的顺序）。

如果 n 是质数，则表达式 (is_prime >> (MAX-n-1)) & 1 将是 1； 0否则：

def is_prime(n):
    return bool((is_prime_var >> (MAX-n-1)) & 1)

您可以使用中的 primes() 作为素数生成器。

thers 也关于埃拉托色尼的快速和高效记忆筛法。可能也很有趣。

Answer 3

您可以使用以下代码。它结合使用埃拉托色尼筛法和生成器函数，以减少该算法的内存使用量。它还利用了一个鲜为人知的事实，即每个大于 4 的素数都可以写成 6*n ± 1。

import math

limit = 2 ** 63 - 1

def isPrim(n, belowPrims):
    limit = int(math.sqrt(n))
    for prim in belowPrims:
        if prim > limit: break
        if n % prim == 0: return False 
    return True

def calcPrims():
    yield 2
    yield 3
    toTest, nextN = [], 6
    while True:
        p1 = nextN - 1
        if isPrim(p1, toTest):
            yield p1
            toTest.append(p1)
        p2 = nextN + 1
        if isPrim(p2, toTest):
            yield p2
            toTest.append(p2)
        nextN += 6

for prim in calcPrims():
    if prim > limit:
        break
    print(prim)

编辑

这里link这里https://primes.utm.edu/notes/faq/six.html简单解释了为什么每个素数都可以写成6*n±1的形式。

如何在 Python 中获得 2^63 - 1 内的素数集合

How to get a prime collection within 2^63 - 1 in Python

python

arrays

primes