素数チェック

このきじは ひらがなでよめません。ごめんなさい。編集者向け:作成する

(ひらがな記事(きじ)について)

素数は、正の整数のうち、1とそれ自身のみを約数として持つ数のことである (整数Nの約数とは、整数Nを割り切れる整数を指す)。

素数の例：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,...

素数を見つける方法

素数は無限に存在する (ユークリッドの定理を参照)。したがって、すべての素数の一覧表を作るのは不可能であり、ある数が素数かどうかを調べるには、その場で判定するしかない。次に、具体的な方法を取り上げる。

試し割り

試し割りとは、ある数Nが素数かどうかを調べるために、約数になる可能性がある数でひととおり割ってみる方法である。割った結果余りがなければ、その数はNの約数なので、1とその数以外の約数をもつことになり、調べる数が素数ではなかったことがわかる。

ある数の約数を調べると、それぞれの約数は常にもう1つの約数とペアになっている（ただし、ある数が、数nの2乗で表せる場合は、同じ数n同士のペアになる）。たとえば、12の約数は、1 ↔ 12、2 ↔ 6、 3 ↔ 4の3つのペアになっている。逆に考えれば、1、2、3が12の約数でなければ、ペアの値12、6、4も約数ではないはずだ。

この考え方を使えば、 「2 〜 nの平方根」の範囲にnの約数がなければ、nは素数であることがわかる（さらに、素数以外の数を約数にもつ場合は、かならずその数より小さい素数の約数も存在するはずなので、この範囲の素数についてのみ調べればよい）。

ある数が約数であるかどうかを調べるには、() を () で割った余り ブロックを使用して、余りが0であるかどうかを確認すればよい。

また、試しに割っていく過程で1つでも約数が見つかった場合は、もとの数が素数でないことがわかるため、それ以上の試し割りは終了して、その時点でスクリプトを停止すればよい。

 メモ:

素数を小さい数から順番にどんどん生成していく場合は、すでに判明している素数をつかって約数チェックを行うよう、次のスクリプトを変更すべきである。

スクリプト

このスクリプトは、与えられた数nが素数かどうかを調べて、その結果を、変数 結果に真偽値 (true/false) で入れる。

 メモ:

次のブロック定義では、「画面を再描画せずに実行する」オプションをオンにすることを、必須ではないが強くお勧めする (特に大きな数を調べるとき)。

定義 (n) は素数?
[約数候補 v] を [2] にする
[結果 v] を [true] にする// 最初に、nが素数であると仮定する。違ったら、後から修正
もし <(n) < (2)> なら // この場合、無条件に素数でない
[結果 v] を [false] にする
でなければ
<(約数候補) > ((n)の[平方根 v]::operators)> まで繰り返す
もし <((n) を (約数候補) で割った余り) = [0]> なら
[結果 v] を [false] にする
[このスクリプトを止める v]
end
[約数候補 v] を (1) ずつ変える
end
end

 メモ:

コードは少しわかりづらくなるが、事前に繰り返し回数を計算しておいたほうが、ループするたびの条件判定がなくなるため、より効率的なコードになる。