处理 1000000 多个元素的列表

Question

我正在尝试找到一种方法来找到小于 100,000,000 的素数的 prime gaps 分布。

我的方法：

第 1 步：从一个 TXT 文件开始 "primes.txt"，其中包含素数列表（最多 10,000,000）。

第 2 步：让程序读取文件，然后将每个数字插入到列表中，p1。

第三步：求上界的平方根（TXT文件中素数上界的10倍，本例中为100,000,000）并创建另一个列表，p2，所有小于或等于该平方根的素数，四舍五入。

第 4 步：定义一个 isPrime() 方法来检查输入是否为素数（N.B.: 因为我知道检查的都是小于100,000,000，我只要检查这个数是否能被所有小于等于100,000,000的平方根的素数整除，也就是10,000)

第5步：添加一个列表l，收集所有素数间隔，然后从1迭代到100,000,000，检查每个数的素数。如果这个数是质数，那么记录它和它之前最后一个质数的差距，同样写到另一个文件"primes2.txt".

第六步：输出列表l.

问题：

该程序似乎需要很长时间才能运行。我感觉问题与我管理列表的方式有关，因为它的大小（Prime Number Theorem 估计来自 "primes.txt" 的列表中大约有 620,420 个元素）。有没有办法通过以不同方式处理列表来减少此程序的运行时间？

我在下面附上了我的代码。

import math
import sys

f = open("primes.txt","r")
p1 = []
for i in f:
    p1.append(int(i))
f.close()
ml = 10000000
ms = math.sqrt(10*ml)
p2 = []
x1 = 0
while x1 < len(p1) and p1[x1] <= int(ms+0.5):
    p2.append(p1[x1])
    x1 += 1

def isPrime(n):
    for i in p2:
        if n%i == 0:
            if n/i == 1:
                return True
            return False
    return True

def main():
    l = [0]*1001 #1,2,4,6,8,10,12,...,2000 (1, and then all evens up to 2000)
    lastprime = -1
    diff = 0
    fileobject = open("primes2.txt",'w')
    for i in xrange(1,10*ml):
        if isPrime(i):
            if i > 2:
                diff = i - lastprime
                if diff == 1:
                    l[0] += 1
                else:
                    l[diff/2] += 1
            lastprime = i
            fileobject.write(str(i)+"\n")
        if i%(ml/100) == 0:
            print i/float(ml/10), "% complete"
    fileobject.close()
    print l

main()

编辑：更改了程序从文件读取的方式

Answer 1

使用埃拉托色尼筛法升级素数函数。这是 link:

Sieve of Eratosthenes - Finding Primes Python

Answer 2

提示：

对于前几百万，您可以像从文件中读取素数一样快地生成素数，但是您需要高效地进行。见下文。（在我最近的 MacBook Pro 上生成 n 高达 1 亿在 Python 上大约需要 7 秒。生成高达 100,000,000 的素数需要 4 分钟。在 PyPy 和 way 在 C 或 Swift 或 Python 和 Numpy 中更快）
你记性太粗心了。示例：ps = f.read().split('\n') 然后使用
p1 = [int(i) for i in ps] 而 ps 位于未使用的内存中。浪费。使用逐行读取文件的循环，以便更有效地使用内存。当您逐行阅读时，文件不会在转换后闲置在内存中。
大素数对密码学有用是有充分理由的；它们需要很长时间才能生成。 Python 不是解决这个问题的最有效语言。

这里有埃拉托色尼筛法可供尝试：

def sieve_of_e(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]

处理 1000000 多个元素的列表

Handling a List of 1000000+ Elements

python

list

large-data