なでしこで素数判定する

プログラミングのレベルアップを考えた時、何かのお題を解くというのはとても役に立ちます。「素数判定」をお題にして、プログラミング力アップを目指しましょう！なでしこで素数判定のプログラムを作ってみます。

問題 - 素数判定

今回考えたいのは、次のようなプログラムです。

素数判定を行うプログラムを作ってください。そして、1から100までの自然数が素数かどうかを順番に判定してください。

このプログラム、何も見ずに作ることができるでしょうか。

(ヒント) 素数とは

Wikipediaによる素数の説明は次の通りです。

素数（そすう、英: primeあるいはprime number）とは、2以上の自然数で、正の約数が1と自分自身のみであるもののことである。正の約数の個数が2である自然数と言い換えることもできる。... 最小の素数は2である。

つまり、正の整数Nが、(N-1)以下のどの整数でも割りきれない数が素数ということです。

例えば、どんな数が素数なのか？

ほぼ問題の答えでもあるのですが、素数がどんな数なのか確認してみましょう。

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,…

一番簡単な実装

「正の整数Nが、(N-1)以下のどの整数でも割りきれない数が素数」という点から、実直にプログラムを作ると以下のようになります。

●(Nを)素数判定とは：
　　　　もし、N<2ならば、いいえを戻す
　　　　もし、N=2ならば、はいを戻す
　　　　Iを2から(N-1)まで繰り返す：
　　　　　　　　もし、N％I＝0ならば、いいえを戻す。
　　　　それははい。
# テスト
Nを1から100まで繰り返す：
　　　　Nを素数判定。
　　　　もし、そうならば：
　　　　　　　　「{N}: 素数」を表示。
　　　　違えば：
　　　　　　　　「{N}: ー」を表示。

素数の特徴を掴んだ最適化を行う

もう少し、素数の特徴を考慮してみましょう。

まず、偶数の素数は2のみです。そこで、偶数であればすぐに、素数ではないという処理を入れましょう。
また、素数かどうかを判定する「繰り返し」文ですが、Nの平方根まで確認すれば、素数と判定して良いようです。この特徴も加味してみましょう。

●(Nを)素数判定とは：
　　　　もし、N<2ならば、いいえを戻す
　　　　もし、N=2ならば、はいを戻す
　　　　もし、N%2=0ならば、いいえを戻す
　　　　Iを2から(INT(平方根(N-1))+1)まで繰り返す：
　　　　　　　　もし、N％I＝0ならば、いいえを戻す。
　　　　それははい。
# テスト
Nを1から100まで繰り返す：
　　　　Nを素数判定。
　　　　もし、そうならば：
　　　　　　　　「{N}: 素数」を表示。
　　　　違えば：
　　　　　　　　「{N}: ー」を表示。

プログラムの行数が数行増えただけですが、実行時間はかなり短くなります。

エラトステネスの篩(ふるい)

素数を検索すると、必ず出てくるのが、エラトステネスの篩という手法です。こちらもWikipediaが非常に詳しいので、詳しい解説は以下にゆずりますが、なでしこでも作ってみましょう！

上記のエラトステネスの篩(ふるい)をそのまま、なでしこで実装すると以下のようになります。

●(Nの)エラトステネス篩とは：
　　　　結果＝[]
　　　　候補=[NG, NG]。
　　　　(N-2)回、候補にOKを配列追加。
　　　　Pを2から(N-1)まで繰り返す：
　　　　　　　　もし、候補[P]ならば：
　　　　　　　　　　　　結果にPを配列追加。
　　　　　　　　　　　　PP＝P×P
　　　　　　　　　　　　QをPPから(N-1)までPずつ増やし繰り返す：
　　　　　　　　　　　　　　　　候補[Q]=NG
　　　　Iで候補を反復：
　　　　　　　　もし、候補[I]ならば：
　　　　　　　　　　　　結果にIを配列追加。
　　　　結果を戻す。

# 100以下の素数を求める
素数一覧＝100のエラトステネス篩。

# プログラムの出力をお題に合わせる
素数配列＝[]。100回、素数配列にNGを配列追加。
素数一覧を反復：
　　　　素数配列[対象] = OK
Nを1から100まで繰り返す：
　　　　もし、素数配列[N]ならば：
　　　　　　「{N}: 素数」と表示。
　　　　違えば：
　　　　　　「{N}: ー」と表示。

まとめ

素数に関するプログラムを、なでしこで作ると、こんな感じになります。
頭の体操で皆さんも素数判定に挑戦してみるのはどうでしょうか。