Q16 既約分数はいくつある？

PHPのソース

<?php
Solve(     20);
Solve(1234567);

function Solve($pSum)
{
    $Answer = 0;
    for($I = 1 ; $I <= $pSum ; $I++){
        $Bunsi = $I;
        $Bunbo = $pSum - $I;
        if ($Bunbo <= $Bunsi) break;
        $GCD = DeriveGCD($Bunsi , $Bunbo);
        if ($GCD == 1){
            $Answer++;
            //printf("%d / %d は1未満の既約分数" , $Bunsi , $Bunbo);
            //echo PHP_EOL;
        }
    }
    printf('1未満の既約分数は、%d通り',$Answer);
    echo PHP_EOL;
}

//ユークリッドの互除法で2数の最大公約数を求める
function DeriveGCD($pVal1, $pVal2)
{
    $WarareruKazu = max($pVal1,$pVal2);
    $WaruKazu = min($pVal1,$pVal2);
    while(true){
        $Amari = $WarareruKazu % $WaruKazu;
        if ($Amari == 0) return $WaruKazu;
        $WarareruKazu = $WaruKazu;
        $WaruKazu = $Amari;
    }
}

実行結果

1未満の既約分数は、4通り
1未満の既約分数は、612360通り

解説

ユークリッドの互除法で互いに素かを判定してます。