目次：プログラミング学習

今回のプログラミング学習は素数を判定するプログラムを作ります。

素数

素数（そすう、英: prime number）とは、1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。 出典:素数 - Wikipedia

素数判定のアルゴリズムはいくつかあります。 素数判定 - Wikipedia

「試し割り」が最も理解しやすいアルゴリズムだと思いますので、上記の Wikipedia ページを参考にしてプログラミングしてみてください。

今回は「ウィルソンの定理」を使って素数判定のプログラムを作ってみようと思います。
（この定理では大きな数を判定するこには計算量が膨大になり実用的ではありません。）

ウィルソンの定理

ウィルソンの定理 ― p が素数ならば (p − 1)! ≡ −1 (mod p) が成り立つ。
逆に、整数 p > 1 に対し、(p − 1)! ≡ −1 (mod p) ならば、p は素数である。
ウィルソンの定理 - Wikipedia

階乗

(p - 1)! は (p - 1)の階乗です。 P が ３ であれば ( 3 - 1)! は 2! = 2 × 1 となります。

≡ (合同)

次の「 ≡ 」はイコールではありません。合同です。

整数論にて、合同記号の左右の整数の値を括弧内のmodで示した値で割った余りが等しいことを示す「合同式」に用いられる。 合同記号 - Wikipedia

(p − 1)! ≡ −1 (mod p)

この式は (p - 1)! を p で割った余りと -1 を p で割った余りが同じであるという意味です。

合同記号を間違えてイコールとみてしまうと、(p - 1)! は -1 を p で割った余りと同じと読んでしまいますね。そう読んでしまう気持ちはわかります。

負の割り算、商と余り

負の数の割り算は中学レベルの計算だから簡単だ！と思いますが、負の数を正の数で割った時の商と余りって何だっけ？ってなりませんか？

(割られる数) ÷ (割る数) = (商) + (余り)

この時、-5 ÷ 2 = (-2) + (-1) 、商が -2 で 余りが -1 だなんて考えちゃう人が多いような気がします。気持ちはわかります。

余りは０か正の整数です。上の式の場合、2 で割った時の余りは、０か１です。

-5 ÷ 2 = (-3) + 1 、商は -3 余りは 1 が正解です。

-5 = 2 × -3 + 1 （割られる数） = (割る数) × (商) + (余り)

ウィルソンの定理を使った素数判定

p が素数であり、かつ 1 より大きい場合 (p - 1)! を p で割った余りと -1 を p で割った余りが同じである。

階乗計算

1
2
3
4
5
6
7
fn factorial(n: u128) -> u128 {
    if n <= 1 {
        1
    } else {
        n * factorial(n - 1)
    }
}

-1 を p で割った余り

-1 を p で割った時の余りは、 p - 1 です。

-1 = p × A + n

0 <= n < p、A = -1

-1 = -p + n

知りたい数は n なので、整理すると

n = p - 1

判定

(p - 1)! mod p = p - 1 であれば素数

# プログラム

1
2
3
4
5
6
7
8
9
10
fn main() {
    print!("1, ");
    for p in 2..33 {
        let n = p - 1;
        if factorial(n) % p == n { // (p - 1 )! を p で割った余り = p - 1
            print!("{}, ", p);
        }
    }
    print!("\n");
}

実行

1
2
$ cargo run
1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 

p が 30 の時の (p - 1)! = 8,841,761,993,739,701,954,543,616,000,000

数が大きくなりすぎるので実用的ではないというのがわかると思います

まとめ

今回は実用的ではない方法でプログラムを作りましたが、プログラミングを学習するための練習にはなったと思います。 定理を正しく理解する必要があります。計算式を自然言語で表現してみるというのも理解する助けになります。 プログラミングを行う前に自然言語で書いたりフローチャートを作成することで仕様を理解しミスを減らしましょう。

追加

for 文禁止とか % 禁止という制約でプログラミングしてみてください。かなりプログラミングスキルが上がると思います。 プログラミングスキルというより検索力かもしれませんが、、、