兩個非常相似的代碼生成n下的素數但CPU時間差異很大

這兩個非常相似的代碼具有非常不同的速度。我不明白爲什麼。第一個比第二個（5s）慢得多（2分鐘）。兩個非常相似的代碼生成n下的素數但CPU時間差異很大

from numpy import sqrt 
primes = [2] 
for i in range(3, 1000000): 
    sq = int(sqrt(i)) 
    aux = False 
    for j in primes: 
     if j>sq: 
      aux = True 
     elif i%j==0: 
      break 
    if aux: 
     primes.append(i)

=========================================== =======================

def isPrime(p, primes): 
     bound = numpy.sqrt(p) 
     i = 0 
     while(primes[i] <= bound): 
      if p % primes[i] == 0: 
       return False 
      i += 1 
     return True 

def compute_primes(bound): 
    primes = [] 
    primes.append(2) 
    for n in range(3, bound): 
     answer = isPrime(n, primes) 
     if answer: 
      primes.append(n) 
    return primes 

compute_primes(1000000)

來源

2016-04-08 gus87

第一個具有無效的壓痕。 Python不會運行它。 – recursive

[強制通知]（https://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth）。 –

其原因性能不同的是，第一個版本不破壞內循環時的上限是到達第二位的位置。假設兩個版本都在檢查11是否爲素數。第一個版本將運行所有較小素數的內循環(2, 3, 5, 7)，其中第二個將僅檢查小於或等於sqrt(11)的值：(2, 3)。

如果你改變了第一個版本，打破達到他們大致的運行，同時上時，界：

if j > sq: 
    aux = True 
    break

來源

2016-04-08 15:52:18 niemmi

兩個非常相似的代碼生成n下的素數但CPU時間差異很大

回答

相關問題