我怎样才能加快我的Python程序？

Question

我试图在Python 3.4.1中创建一个程序来获取2到100,000的素数。

我的问题是，它需要太多的时间来处理所有的信息，它永远不会给我任何结果。

我已经离开了大约半个小时，它减慢了我所有的电脑，它并没有给我我想要的东西。

我正在使用Eratosthenes的筛算法"Criba de Eratostenes"。

这里是我的代码：

from math import * 

def primos(num): 
    num2  = num + 1 
    tnumeros = []      # tnumeros = every number from 2 to num 
    npnumeros= []      # npnumeros = every number that is no prime 
    pnumeros = []      # pnumeros = every prime number 

    for a in range(2, num2): 
     tnumeros.append(a) 

    for i in range(2, int(sqrt(num)) + 1): 
     for j in range(i, int(num/i) + 1): 
      np = i * j 
      npnumeros.append(np) 

    npnumeros = list(set(npnumeros)) 

    for e in tnumeros: 
     if (e in npnumeros): 
      continue 
     else: 
      pnumeros.append(e) 

    return (str("".join(str(pnumeros)))) 

print(primos(100000)) 

Answer 1

不要使用单供npnumeros值;改用集合。你只是在寻找一个号码是否是集合中的感兴趣，所以使它成为一个集从开始：

npnumeros = set() 
# ... 
for i in range(2, int(sqrt(num)) + 1): 
    for j in range(i, int(num/i) + 1): 
     np = i * j 
     npnumeros.add(np) 

# npnumeros = list(set(npnumeros)) # Remove this line, it's no longer needed 

for e in tnumeros: 
    if (e in npnumeros): 
     continue 
    else: 
     pnumeros.append(e) 

原因你的代码是缓慢的是，在列表中查找数为O（N ）时间，并且在O（N）循环内做O（N^2）时间。但是在一个集合中查找数字是O（1）次，所以你将在该循环内部有O（N）个时间。从O（N^2）到O（N）将代表处理速度的巨大差异。

如果您不明白我使用的O（N）表示法，请参阅Google "Big O notation"以了解更多信息。

Answer 2

这是一个严重的截断答案，因为这个问题可能应该移到CR。

一个快速加速就是将npnumeros作为一个集合而不是一个列表。这意味着后面的计算if (e in npnumeros):会显着加快。

修改后的代码：

from math import * 

def primos(num): 
    num2  = num + 1 
    tnumeros = []      # tnumeros = every number from 2 to num 
    npnumeros= []      # npnumeros = every number that is no prime 
    pnumeros = []      # pnumeros = every prime number 

    for a in range(2, num2): 
     tnumeros.append(a) 

    for i in range(2, int(sqrt(num)) + 1): 
     for j in range(i, int(num/i) + 1): 
      np = i * j 
      npnumeros.append(np) 

    npnumeros = set(npnumeros) 

    for e in tnumeros: 
     if (e in npnumeros): 
      continue 
     else: 
      pnumeros.append(e) 

    return (str("".join(str(pnumeros)))) 

print(primos(100000)) 

运行更快〜60倍。