まずは総当たりで割り算してみる。
<?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(切り上げ)にしたがこれで正しかったか(正確かどうか)はちょっとよく分からない。
コメント