数字がPythonでプライムであるかどうかをテストする最速の方法

Question

私はPythonを使用して数字が素数であるかどうかを判断するための迅速な方法を得ようとしています。

私はこれを行う2つの機能を持っています。両方ともTrueまたはFalseを返します。

関数isPrime1は非常に高速です。Falseは、数値が素数ではありません。例えば、大きい数字で。しかし、大きな素数に対してTrueをテストするのは遅いです。

関数isPrime2は、素数に対してTrueを返す方が高速です。しかし、数値が大きくプライムでない場合、値を返すには時間がかかります。最初の機能はそれでうまく機能します。

私は素数ではない大きな数字に対して素早くFalseを返すことができ、素数である大きな数字ですばやく動作するソリューションを考案できますか？

`

def isPrime1(number): #Works well with big numbers that are not prime 
    state = True 
    if number <= 0: 
     state = False 
     return state 
    else:   
     for i in range(2,number): 
      if number % i == 0: 
       state = False 
       break 
     return state 

def isPrime2(number): #Works well with big numbers that are prime 
    d = 2 
    while d*d <= number: 
     while (number % d) == 0:    
      number //= d 
     d += 1 
    if number > 1:  
     return True 
    else: 
     return False` 

Answer 1

素数のテストは非常にトリッキーな話題です。

コードをスピードアップする前に、意図したとおりに動作することを確認してください。 非常に単純なアルゴリズムから始め、そこから構築することをお勧めします。

興味深いことに、isPrime2に欠陥があります。 number Dの要因は、数はnumber = number // dにしての終了時に更新されて発見された場合には

ライン3〜6非常に

while d*d <= number: 
    while (number % d) == 0:    
     number //= d 
    d += 1 

を言っている...、12、10、6のためにTrueを返しますwhileループ、数> 1あなたはnumber = 6でコードを作業するTrue

を返す場合：

isPrime2(6) 
initialise> number := 6 
initialise> d := 2 
line3> check (2 * 2 < 6)  :True 
line4> check (6 % 2 == 0) :True 
line5> update (number := 6//2) -> number = 3 
line6> update (d : d + 1) -> d = 3 
jump to line3 
line3> check (3 * 3 < 3)  :False -> GOTO line7 
line7> check(number > 1) -> check(3 > 1) :True 
line8> return True -> 6 is prime 

Answer 2

ここれます私が思いついたもの

def is_prime(number): 
    # if number is equal to or less than 1, return False 
    if number <= 1: 
     return False 

    for x in range(2, number): 
     # if number is divisble by x, return False 
     if not number % x: 
      return False 
    return True 

Answer 3

平方根があなたが考えることができる最も単純なものまでです。その最悪の場合は、すべての部門が実行されなければならないので、素数です。とにかく、10億になるまで、実質的に測定可能な時間はありません（1000000007の約1.2ミリ秒）。

def Prime(n): 
    if n & 1 == 0: 
     return 2 
    d= 3 
    while d * d <= n: 
     if n % d == 0: 
      return d 
     d= d + 2 
    return 0 

このバージョンは最小除数又は0なく、ブール値を返すことに注意してください。

いくつかのマイクロ最適化が可能です（増分テーブルを使用するなど）が、大きな利益を得ることはできません。

もっと洗練された方法がありますが、そのような小さなもののために大騒ぎに値するとは確信できません。n