PHPで約数の総数が偶数か奇数かを判定するプログラムの書き方

与えられた数の約数の総数が偶数か奇数かを判定したい場合、以下のようなPHPコードを使用します。

サンプルコード

<?php
function divisor_count($my_val)
{
    $my_count = 0;
    for ($i = 1; $i <= sqrt($my_val) + 1; $i++)
    {
        if ($my_val % $i == 0)
        $my_count += ($my_val / $i == $i)? 1 : 2;
    }
    if ($my_count % 2 == 0)
        echo "It is an even number\n";
    else
        echo "It is an odd number\n";
}
divisor_count(100);
?>

出力結果

It is an odd number

コードの解説

このプログラムでは、まず「divisor_count」という名前の関数を定義しています。この関数は、引数として渡された数値の約数の個数を計算する役割を担います。

約数の個数を効率よく求めるポイントは、ループ範囲を「1からその数の平方根まで」に限定することです。$i が $my_val を割り切れる場合、$my_val / $i と $i が等しければ(つまり $i が平方根に一致する場合)カウントを1だけ増やし、そうでなければ約数はペアで存在するため2を加算します。これにより、全ての数を順番に調べるよりも計算量を大幅に抑えられます。

最後に、合計した約数の個数を2で割った余りを確認します。余りが0であれば偶数、それ以外であれば奇数として、対応するメッセージが出力されます。

数学的な補足

実は、「約数の個数が奇数になるのは、その数が完全平方数である場合のみ」という有名な性質があります。これは、約数が通常ペアで現れるのに対し、完全平方数では平方根に相当する約数だけが単独で存在するためです。

上記の例では、100 = 10² という完全平方数であり、実際の約数は 1, 2, 4, 5, 10, 20, 25, 50, 100 の9個となるため、奇数と判定されるわけです。