戯言。PHPでグロタンディーク素数が素数かどうか確認する。

パイザ問題集のグロタンディーク変数の問題をPHPで解いてみた。

グロタンディークという数学者が適当な素数として「57」を例に挙げたらしい。

…ところが、57は素数ではなかったらしい。不名誉にもそれが歴史に残った。

本当に素数じゃないのか調べてみたところ、結果的には3と19で割り切れることがわかりました。

    $s = 57;
    
    // 2以上でないなら素数ではない
    if($s < 2){
        echo "NO";
        exit(1);
    }
    
    $count = 0;
    $list = [];
    
    // 1～$S以下の数字で割って、あまりが出る数を$countに求める。
    for($i = 1; $i < $s; $i++){
        $a = $s % $i;
        if($a === 0) {
            $count++;
            $list[] = $i;
        }
    }
    
    // 割り切れた数は？ => 1, 3, 19
    // var_dump($list);
    // exit(1);
    
    if($count == 1){
        echo "YES";
    }else{
        echo "NO";
    }

とりあえず力技のループ処理で解いたが、素数を求める効率的なアルゴリズムは無数にあるので、そのへんを今後学んで行きたい。