今回の記事では、ある自然数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さんの指摘内容を参考に素数を求める手順を変更致しました
実際に上記を元にコードを書いてみました
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
↑上記のサイトに書いてあるアルゴリズムを元にコードを書いてみました
#####エラトステネスの篩
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は素数ではない理由と判定方法!最大の素数も!