【最大公約数】STEP: 3 素数判定 (paizaランク C 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【最大公約数】STEP: 3 素数判定 (paizaランク C 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
だからね…アルゴリズムね…分かんないんだって(´；ω；`)
解説を見て、別言語のサンプルコードを何となく「PHP言語ならこうかな？」っとコードを書いたら通過できました。原理としては、「$i = 2」から繰り返し処理でNにまでに割り切れる数があったら「素数ではない」という判定が下せます。ただ巨大な数値がテストケースにあり、アルゴリズムを駆使しないとタイムオーバーになります。
解説によるとNの0.5乗まで繰り返せば同様の結果が得られるとのこと。理由は理解できませんでした(;^ω^)
Ｎの平方根を用意し、繰り返し処理で素数を検査します。
素数を数えて落ち着く…どころか発狂するわ！(# ﾟДﾟ)
解答例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
<?php $n = trim(fgets(STDIN)); $flag = true; if($n == 1){ $flag = false; } $m = round(sqrt($n)); for($i = 2;$i <= $m;$i++){ if($n % $i == 0){ $flag = false; break; } } if($flag == true){ echo "YES"; } else { echo "NO"; } ?> |
