nの下で素数を生成するのに非常に似ている2つのコード、しかし非常に異なるCPU時間

Question

これら2つの非常によく似たコードは、速度が非常に異なります。なぜか分からない。最初のものは2番目のもの（5秒）よりずっと遅い（2分）。

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) 

Answer 1

パフォーマンスの違いの理由は上限があるときに最初のバージョンは内部ループを破壊しないということです第2のものと同じように到達した。両方のバージョンが11がプライムであるかどうかをチェックしているとします。最初のバージョンでは、すべての小さな素数(2, 3, 5, 7)に対して内側ループが実行されます.2番目のバージョンでは、sqrt(11)：(2, 3)より小さいか等しい値だけがチェックされます。

あなたは、彼らがほぼ同じ時間に実行達したときに上限破るために最初のバージョンを変更する場合：

if j > sq: 
    aux = True 
    break