プライム検索のプロセスをスピードアップするには？

Question

問題が発生したときに私はProject Eulerで問題7を実行していました。私のコードは完成まで長い間かかっていました。ここに私のコードです。

def Problem7(): 
    num = 0 
    p = 0 
    while p < 10002 : 
     prime = True 
     for i in range(2,num): 
      if (num%i==0): 
       prime = False 
     if prime: 
      print(num) 
      p = p + 1 
     num = num + 1 
Problem7() 

どうすれば速くできますか？別の方法がありますか？

Answer 1

p変数が格納していると思われる最後の部分に素数を表示してください。

コメントに記載されているように、よりスマートなアルゴリズムで多くの計算を省略できます。

1：数が偶数（NUM％2）であるかどうかを確認し（したがって、素数でない場合）

2：除数は平方根とプライム== trueの場合、試験除数以下であるが

3：あなたは、超効率的に取得したい、まだ素数でない場合は、2によって増分ので、あなたが奇数のみをテスト（すべて追いついたがNUM％2で確認した）

場合は、プライムではありません、すべての数は、少なくとも一つを有しますプライムファクタなので、配列内で見つかった各素数を格納し、配列内の最高のものだけをチェックすることができます...しかし、それは必要ではない余分なコーディングがたくさんありますこの問題に。上記のロジックを使用して、テスト実行時に数秒で最初の10,000個の素数を見つけました。

数字100を考えると、ロジックは99の可能な除数をテストします。上記のロジックは2回だけテストして停止します。平方根に行く最悪の場合は、2,3,5,7,9 ... 5の計算ではなく、99の代わりになります。

Answer 2

次の方法を使用して、数値が素数であるかどうかを確認しました（0m0.612s ）：

import math 

def is_prime(num): 
    if num == 0 or num == 1: 
     return False 
    if num == 2: 
     return True 
    temp = 2 
    while temp < math.sqrt(num) + 1: 
     if num % temp == 0: 
      return False 
     temp += 1 

    return True