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

問題

解答

素因数分解の条件式$i * $i <= $numの必要性

1.処理時間の短縮

num の平方根よりも大きい数は、num の素因数になり得ません。なぜなら、平方根よりも大きい数の積は常に num より大きくなるからです。

例えば、num = 15 の場合、平方根は約 3.87 です。つまり、4 以上のすべての数は 15 の素因数候補から除外できます。

この条件式を導入することで、無駄なループ処理を大幅に削減でき、処理時間を短縮することができます。

2.探索範囲の絞り込み

i * i <= num という条件は、i が num の最大限素因候補となり得る値を明確に示しています。

例えば、num = 20 の場合、この条件式は i <= 4 となり、i として検討すべき値は 1, 2, 3, 4 のみに絞られます。

このように、i * i <= num 条件式は、探索範囲を効率的に絞り込む効果がある。

<?php
    function primeFactors($num) {
        $factors = array();
        // 2で限界まで割る
        while ($num % 2 == 0) {
            $factors[] = 2;
            $num /=2;
        }
        // 素因数分解
        for($i = 3; $i * $i <= $num; $i += 2) {
            while ($num % $i == 0) {
                $factors[] = $i;
                $num /= $i;
            }
        }
        if($num > 2) {
            $factors[] = $num;
        }
        return $factors;
    }
    
    $n = trim(fgets(STDIN));
    $factors = primeFactors($n);
    foreach ($factors as $v) {
        echo $v."\n";
    } 
    
?>