戯言。PHPで素数判定するアルゴリズムのコード実装を行った。

まずは総当たりで割り算してみる。

<?php
    // 自分の得意な言語で
    // Let's チャレンジ！！
    $a = trim(fgets(STDIN));
    
    // 2より小さいなら素数ではない
    if($a < 2){
        echo "NO";
        exit(1);
    }
    
    $c = 0;
    for($i = 2; $i < $a; $i++){
        // 1度でも割り切れたら素数ではない
        if(($a % $i) == 0){
            echo "NO";
            exit(1);
        }
    }
    
    // 1度も割り切れてないので素数
    echo "YES";
    exit(1);
    
?>

paizaの問題集で実行したら結果は正しいが「Runtime Error」になった。

何度か動かしてみるとRuntime Errorはexit(1);のところで起こっていることがわかった。

0を渡さないからエラーになっていた（汗）ので以下のように修正した。

<?php
    // 自分の得意な言語で
    // Let's チャレンジ！！
    $a = trim(fgets(STDIN));
    // echo "YES";
        
    // 2より小さいなら素数ではない
    if($a < 2){
        echo "NO";
        exit();
    }
    
    // 2なら素数
    if($a == 2){
        echo "YES";
        exit();
    }
    
    // 2で割れたら素数ではない
    if(($a % 2) == 0){
        echo "NO";
        exit();
    }
    
    $c = 0;
    for($i = 3; $i < $a; ($i = $i + 2) ){
        // 1度でも割り切れたら素数ではない
        if(($a % $i) == 0){
            echo "NO";
            exit();
        }
    }
    
    // 1度も割り切れてないので素数
    echo "YES";
    exit();
    
?>

100万までの数値であれば、これで判定できるが、10^12以上になると16秒で処理が終わらないので工夫が必要になる。

整数nは√n以下の数で割り切れないならば素数と言えるそうだ。

合成数を構成する値が√n以上にならないからしいが、

いくつかWebの解説を読んだがわかったようでわからなかったが、とりあえず実装してみる。

<?php
    // 自分の得意な言語で
    // Let's チャレンジ！！
    $a = trim(fgets(STDIN));
    // echo "YES";
        
    // 2より小さいなら素数ではない
    if($a < 2){
        echo "NO";
        exit();
    }
    
    // 2なら素数
    if($a == 2){
        echo "YES";
        exit();
    }
    
    // 2で割れたら素数ではない
    if(($a % 2) == 0){
        echo "NO";
        exit();
    }
    
    $c = 0;
    for($i = 3; $i < ceil(sqrt($a)); ($i = $i + 2) ){
        // 1度でも割り切れたら素数ではない
        if(($a % $i) == 0){
            echo "NO";
            exit();
        }
    }
    
    // 1度も割り切れてないので素数
    echo "YES";
    exit();
    
?>

for文の条件を$aからceil(sprt($a))に変更したら処理速度が劇的に改善された。

ceil(切り上げ)にしたがこれで正しかったか（正確かどうか）はちょっとよく分からない。