Pythonで素数を見つけるためのさまざまな方法の分析

素数は、1またはそれ自体でのみ割り切れる正の整数です。数が素数であるかどうかを見つけることは、長い間興味深いプログラミングの課題です。さらに、さまざまな方法があり、それらはさまざまな効率を持っています。この記事では、そのような3つの方法を検討し、実行のタイミングの観点からどちらがより効率的かを判断します。

すべての除数を確認

これは単純なプログラムであり、1から指定された数より1少ない整数までを取り、その数がこれらのいずれかで除算されるかどうかをチェックし続けます。この数を割ることができる数が見つからない場合、その数は素数です。

例

import time
#Function to check Prime Number
def check_prime(final_val):
   if final_val <= 1:
      return False
   for divisor in range(2,final_val):
      if final_val % divisor == 0:
         return False
      return True
# Track the Start Time
StartTime = time.time()
#Count the number of prime numbers
cnt = 0
for final_val in range(1,10001):
   x = check_prime(final_val)
   cnt += x
print 'Count of prime numbers till',final_val,'is ', cnt
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

出力

上記のコードを実行すると、次の結果が得られます-

Count of prime numbers till 10000 is 1229
Time Elapsed is: 2.3100001812

平方根（N）までの因子

数学的には、チェックしている数の平方根までの因子を見つけるだけで十分であることがわかります。このアプローチは反復回数を減らすため、以下のように確認できるより高速なはずです。このアイデアを実装するためのロジックは次のとおりです。

• プライム値がチェックされている数値の平方根を見つけます。

• 数値を値2から始まる平方根値まで各値で除算し、余りが残っているかどうかを確認します。

• 上記のいずれかのステップで余りがゼロの場合、その数は素数ではありません。

例

import math
import time
def is_prime(final_val):
   # 1 is not a prime number
   if final_val <= 1:
      return False
   i = 2
   while i <= math.floor(math.sqrt(final_val)):
   # Check if any remainders are cerated
      if final_val % i == 0:
         return False
      i += 1
   return True
# Track the Start Time
StartTime = time.time()
cnt = 0
for n in xrange(1, 10001):
   x = is_prime(n)
   cnt += x
print 'Count of prime numbers till',n,'is ', cnt
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

出力

上記のコードを実行すると、次の結果が得られます-

Count of prime numbers till 10000 is 1229
Time Elapsed is: 0.0529999732971

エラトステネスのふるい

この方法では、非素数または合成数を削除して、特定の数まで素数を取得します。それを達成するために私たちが従うステップは以下のとおりです。

• 2からその数までの連続する整数のリストを作成し、それまですべての素数を見つけます。

• 最初の数、つまり2を取り、そのすべての倍数のリストを作成します。元のリストからこの倍数のリストを削除しますが、2は削除しません。次の番号に対してこれを繰り返します。つまり、次の番号に対して3というように繰り返します。数自体ではなく、倍数のみを削除していることに注意してください。したがって、5または11が削除されることはありませんが、10および22が削除されます。

• すべての除去の後、残ったリストは、求められた数までの素数のリストです。

例

import time
def sieve_method(n):
#Create a list of prime numbers
   prime_number_list = []
   for i in range(2, n+1):
# Capture the number if it si not in prime list
   if i not in prime_number_list:
      print (i)
# Add the number to the prime list number if it is a multiple
   for j in range(i*i, n+1, i):
      prime_number_list.append(j)
# Track the Start Time
StartTime = time.time()
cnt = 0
print(sieve_method(25))
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

出力

上記のコードを実行すると、次の結果が得られます-

2
3
5
7
11
13
17
19
23
Time Elapsed is: 0.0