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

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

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

サンプルコードでは、for i in 2:isqrt(n)という範囲でループし、n % i == 0となる数が見つかった時点で素数ではないと判定しています。isqrt()という整数の平方根を求める専用関数がJuliaには用意されています。

初心者がよくつまずくのが、sqrt()とisqrt()の違いです。isqrt()は整数の平方根を整数として返すため、範囲指定にそのまま使いやすい点で便利です。

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