[Python]素数を求めてみる

今回の記事では、ある自然数N以下の素数を表示するプログラムを書いていきます(N>=2)

初投稿

こんにちは、kageyasaiと申します。
qiitaへの投稿は備忘録として使っていきたいと思います
よろしくお願いします。

動作環境

Windows10 Pro
Python3.6.2

素数とは

1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。
素数 - Wikipedia

素数を求める

私が最初に思いついた素数を求める手順を以下に書いていきます。
① 2からNまでの数字を一つずつ取り出す
② 取り出した数字(以下numとする)を2からnum-1までの数字で割る
③ もしnumが割り切れたなら①に戻る

---

2019/2/3追記
偶数の素数って2だけなんですね
そりゃそうか2以外の偶数は2の倍数だからね
また素数の判定には素数で割るといいみたいです

①3からNまでの奇数を一つずつ取り出す
②取り出した数字(以下numとする)を素数リストの要素で割る
③もし素数リストの要素で割れなければ素数リストに追加して①に戻る

@shiracamusさんの指摘内容を参考に素数を求める手順を変更致しました

---

実際に上記を元にコードを書いてみました

Prime_number.py

def get_primenumber(N):
    #素数リスト
    prime_list = [2]
    #3からNまでの数字を一つずつ取り出す
    for num in range(3,N+1,2):
      #取り出した数字が素数リストの要素で割れなければ素数リストに追加する
      if all( num % prime != 0 for prime in prime_list):
        prime_list.append(num)

    return prime_list

def main():
    while True:
      number = int(input("自然数:"))
      if number > 1:
        break
      else:
        print("2以上の自然数を入力してください")
    print(get_primenumber(number))

if __name__ == "__main__":
    main()

get_primenumber(N)が素数を求めている関数です
main()では入力した自然数をget_primenumberに渡しています

実行結果

PS C:\Python\math> python .\Prime_number.py
自然数:100
[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以下の素数を求めれていますね
ただ、今の素数を求める手順だと自然数の値によって処理が終わるまでかなり時間がかかってしまいます
現状の処理時間を計測して簡単にまとめてみました

自然数	処理時間(秒)
100	0.0
1000	0.0029988288
10000	0.0959968566
100000	6.3189933300

10000から100000になると処理時間が約70倍になっています
1000000になると3分待っても終了しませんでした

何か他に素数を求める方法が無いか調べました
調べていくとエラトステネスの篩というアルゴリズムが簡単に素数を求めれそうでした
では実際にエラトステネスの篩を実装していきます
エラトステネスの篩 - Wikipedia
↑上記のサイトに書いてあるアルゴリズムを元にコードを書いてみました

エラトステネスの篩

Eratosthenes.py

import math
#----エラトステネスの篩--------
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)
        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    return prime_list

def main():
    print("""
---------------------------------------------------------------------
  エラトステネスの篩を用いたプログラムです(整数 >= 2)
  ex) 整数:10
      結果:[2,3,5,7]
---------------------------------------------------------------------
    """)
    while True:
      num = int(input("整数:"))
      if num > 1:
        break
    print(get_primenumber(num))
if __name__ == "__main__":
    main()

アルゴリズムが分かっているとコードが書きやすいですね。
実行結果も載せときます

実行結果

PS C:\Python\math> python .\Eratosthenes.py

---------------------------------------------------------------------
  エラトステネスの篩を用いたプログラムです(整数 >= 2)
  ex) 整数:10
      結果:[2,3,5,7]
---------------------------------------------------------------------

整数:100
結果:[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	0.0
1000	0.0
10000	0.0049240589
100000	0.0850005149

100000の時の処理時間が6.31秒から0.085秒になっています
約74倍速くなっています
ちなみに1000000の時だと2.75秒でした
速い( ﾟдﾟ )ｸﾜｯ!!

まとめ

今回はエラトステネスの篩を用いた実装を行いましたが他の素数を求めるアルゴリズムもいつか実装してみたいですね。

これからも先人の知恵をもっと利用していきたいですね

参考

エラトステネスの篩 - Wikipedia
素数 - Wikipedia
【詳しく解説】1は素数ではない理由と判定方法!最大の素数も!