生成大素数列表的有效方法

Question

我想弄清楚的是，当我运行将此代码用于较小的数字时，它 returns 列表就很好，但对于较大的数字（我会在上下文中称其为小我正在做的事情。）像 29996299，它会运行很长一段时间，我已经等了 45 分钟没有结果，最后不得不杀死程序。我想知道是否有更有效的方法来处理规模大于 4 或 5 位的数字。我已经测试了运行ge 函数的一些排列，看看是否有更好的方法来处理我想要生成的列表的限制，但似乎对它花费的时间没有任何影响做计算。我是 python 的新手，作为程序员我不是很有经验。谢谢你的时间。

运行再提交这个程序post，花了一个半小时左右。

程序的功能是获取用户选择的数字，用它来生成下界，找到界和输入之间的所有素数并附加到列表，然后生成第二个上界并找到所有素数然后附加到列表，以创建一个从初始数字向前和向后延伸的列表。该程序像我期望的那样工作，但没有我需要的那么快，因为我要处理的数字会很快变大，每个阶段几乎翻一番。

initial_num = input("Please enter a number. ") 

lower_1 = int(initial_num) - 1000
upper_1 = int(initial_num)
list_1 = []

for num in range(lower_1,upper_1):
   if num > 1:
       for i in range(2,num):
           if (num % i) == 0:
               break
       else:
           list_1.append(num)

lower_2 = list_1[-1]
upper_2 = list_1[-1] + 2000
list_2 = []

for num in range(lower_2,upper_2 +1):
   if num > 1:
       for i in range(2,num):
           if (num % i) == 0:
               break
       else:
           list_2.append(num)

list_3 = list_1 + list_2[1:]

print list_3

Answer 1

您可以使用更高效的算法来生成整个素数列表，最多为N。这就是Sieve of Erathostenes。请查看链接的文章，它甚至包含一个示例伪代码。算法的基本思想是：

维护L，一个潜在素数的列表（最初是从2到N的所有数字）
选择下一个质数 (p) 作为 L 的第一个元素（初始为 2）
删除所有 p 的倍数，直到 N，因为它们不能是素数
从第 2 步开始重复

最后你会得到一个素数列表。

Pyhton 中的实现from here

def eratosthenes2(n):
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
            yield i
            multiples.update(range(i*i, n+1, i))

print(list(eratosthenes2(100)))

为了减少内存消耗，您可以考虑使用一个位集，为每个数字存储一位。这应该将内存使用量减少 32 - 64 倍。位集实现可用于 python here.

生成大素数列表的有效方法

Efficient method for generating lists of large prime numbers

python

performance

math

primes

largenumber