【paizaラーニング】レベルアップ問題集 素数メニュー 「素数大学」 PHP

問題

解答

　1. 最初に取りうる値の最大値を定義します。
　2. 素数判定の関数を定義。
　3. 定義した最大値の大きさの素数判定表を作成。
　4. それに基づいて合格判定の出力。

<?php
    // 最大値の定義
    define("MAX", 6000001);
    
    function sieve($x) {
        $is_prime = array_fill(0, $x + 1, true);
        $is_prime[0] = $is_prime[1] = false;
        // エラトステネスの篩で素数判定
        for($i = 2; $i * $i <= $x; $i++) {
            if($is_prime[$i]) {
                for($j = $i * $i; $j <= $x; $j += $i) {
                    $is_prime[$j] = false;
                }
            }
        }
        return $is_prime;
    }
    
    $primelist = sieve(MAX);
    // 判定表のもと、出力
    $n = trim(fgets(STDIN));
    for($i = 0; $i < $n; $i++ ) {
        $num = trim(fgets(STDIN));
        echo ($num <= MAX && $primelist[$num]) ? "pass" : "failure";
        echo "\n";
    }
?>