アルゴリズムでいこう！- 素数(エラトステネスのふるい)

エラトステネスとは。ギリシアの天文学者，地理学者，詩人。

ヨーロッパでは16世紀にコペルニクスが登場するまで地動説が信じられていましたが、その1700年以上前に地球を球体と考えて、その大きさを測定してしまった人のようです。

エラトステネス

試し割り法を更に効率化するため、「エラトステネスのふるい」という考え方を試してみます。

わかりやすく解説してあります。

def prime_eratosthenes(n):
   prime_list = []
   num_list=[]
   for i in range(2, n+1):
       if i not in num_list:
           prime_list.append(i)
           for j in range(i*i, n+1, i):
               num_list.append(j)
   print(prime_list)

prime_eratosthenes(31)

【Python】高速かつ簡単にNまでの素数を求めるプログラム【エラトステネスの篩】 - d_tail's blog

実装です。こちらは、numpyを使っています。

import numpy as np

def seachPrimeNum(N):
   max = int(np.sqrt(N))
   seachList = [i for i in range(2,N+1)]
   primeNum = []
   while seachList[0] <= max:
       primeNum.append(seachList[0])
       tmp = seachList[0]
       seachList = [i for i in seachList if i % tmp != 0]
   primeNum.extend(seachList)
   return primeNum

print(seachPrimeNum(３１))

出力は両方とも、

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

となります。

考え方ですが、

pythonでエラトステネスのふるい

100までの素数（エラトステネスのふるい）ですふるい落とす段階がわかりやすいです。関数にして少しコードも変更させてもらっています。

def isPrime(n):
   A = list(range(2, n+1)) # 2～nまでの素数候補の集合リスト

   sqrt_n = n ** 0.5　＃求めたい数値の平方根

   print('素数候補',A)　＃まず初期のListを表示

   idx = 0　＃ Listの添字index

   while True:
       p = A[idx] # リストの数値(素数の候補"p")を取り出します
       if p > sqrt_n:
　　　　　　break # 素数の候補の数値"p"が”sqrt_n”を超えたら、ふるい終了

       print('p={}の倍数をふるい落とす'.format(p))

       check_numbers = A[idx+1:] # 素数を除くふるい対象

       for check_number in check_numbers:
           if check_number % p == 0: # 素数pの倍数を集合リストから削除
               A.remove(check_number)

       print(A)

       idx += 1 #次の数値を指定します

   print('{0}までの素数 計{1}個'.format(n, len(A)),A)

isPrime(100)

とすれば、

素数候補 [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
p=2の倍数をふるい落とす
[2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]
p=3の倍数をふるい落とす
[2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97]
p=5の倍数をふるい落とす
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97]
p=7の倍数をふるい落とす
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
100までの素数 計25個 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]