素数かどうかを判定しよう

このレッスンでは、C言語である数が素数かどうかを判定する方法を学び、繰り返し処理を使った基本的な数学アルゴリズムを理解することを目標にします。「C言語 素数判定 実装」で調べている方向けです。

ある数が素数(1とその数自身でしか割り切れない数)かどうかは、2から「その数の平方根」までの数で割り切れるかを調べればわかります。すべて割り切れなければ素数です。

サンプルコードでは、for (int i = 2; i * i <= n; i++)という範囲でループし、n % i == 0となる数が見つかった時点で素数ではないと判定しています。stdbool.hヘッダを使ってbool型の戻り値を扱っている点にも注目してみましょう。

初心者がよくつまずくのが、C言語の古い規格にはbool型がない点です。stdbool.hをインクルードすることで、C99以降の規格でtrue・falseを扱えるようになります。

暗号技術の基礎にも使われる重要な数学的性質で、エラトステネスの篩(ふるい)という、複数の素数を一度に効率よく求める発展的な手法も存在します。