サンプル・プログラム
剰余を使って判定する方法
を例に考える。
筆算の要領で剰余を求めていく。
2340 ％ 555 ＝ 120
1200 ％ 555 ＝ 90
900 ％ 555 ＝ 345
3450 ％ 555 ＝ 120
...
ふたたび120が出てくるので、小数第2位～4位が繰り返される無限小数であることが分かる。
剰余を配列の要素として、ふたたび要素が出てくるかどうかを調べることで、無限小数かどうかを調べることができる。要素の数は、最大でも（分母－１）個である。
途中で剰余が０になれば有限小数である。
素因数分解を使って判定する方法
まず、
を約分すると、 
になる。ここで、剰余を使って判定してもいいのだが、さらに別の方法を使う。有限小数の定義から、分母は
（α，β≧0）である。つまり、分母を素因数分解し、2または5以外の素因数が出てこなければ有限小数ということになる。
185＝5×37 であるから、これは無限小数だ。
では
はどうか――。分子も分母も大きな整数だが、約分すると
と小さくなる。16＝2×2×2×2 であるから、これは有限小数だ。
このように、分数を約分し、分母を素因数分解することで、有限小数かどうかの判定が可能となることが分かった。
PHPでプログラムを作るには、分数の約分を行うのに最大公約数を求める「ユークリッドの互除法」、素因数分解では素数を求める「エラトステネスのふるい」という定番アルゴリズムを用いることにする。
解説：ユークリッドの互除法
0095: /**
0096: * 最大公約数を求める（ユークリッドの互除法）
0097: * @param int $m, $n整数
0098: * @return int最大公約数
0099: */
0100: function gcdEuclidean($m, $n) {
0101: if ($n == 0) return $m;
0102: return gcdEuclidean($n, (int)$m % $n);
0103: }
解説：素因数分解
0125: /**
0126: * 素因数分解
0127: * @param array $primes 素因数を格納する配列
0128: * @param int $n 素因数分解する整数
0129: * @return array $primes
0130: */
0131: function primeDecomposition($n, &$primes) {
0132: $max = floor(sqrt($n));
0133: EratosthenesSieve($max, $primes);
0134:
0135: //2から平方根までの素因数を求める
0136: for ($i = 2; $i <= $max; $i++) {
0137: if (isset($primes[$i])) {
0138: do {
0139: $b = $n % $i;
0140: if ($b == 0) {
0141: $primes[$i]++;
0142: $n = floor($n / $i);
0143: }
0144: } while ($b == 0);
0145: }
0146: }
0147: //残った素数
0148: if ($n > $max) $primes[$n] = 1;
0149:
0150: return $primes;
0151: }
因数が2つ以上ある場合、因数の値は元の整数の平方根より小さいことは自明である。そこで、元の整数の平方根を最大値 $max とし、2以上 $max 以下の素数の一覧を求め、これを配列に格納する。
素数一覧を求めるのに使うのが「エラトステネスのふるい」と呼ばれる定番アルゴリズムだ。その原理については、「Wikipedia：エラトステネスの篩」を参照していただきたい。
エラトステネスのふるいは、ユーザー関数 EratosthenesSieve に実装している。
素数一覧は配列 $primes に入って返される。要素数は、2以上 $max 以下の素数の数だけに絞られる。
素数一覧が求められたら、2以上 $max 以下の整数でループを回し、素因数分解を行う。
ユーザー関数 EratosthenesSieve で得られた素数表 $primes に対し、因数が1個なら値1を、2個なら値2を代入していく。
解説：有限小数かどうか
0153: /**
0154: * 有限小数かどうか
0155: * @param int $denominator分母
0156: * @param int $numerator 分子
0157: * @return bool TRUE/FALSE
0158: */
0159: function isFiniteDecimal($denominator, $numerator) {
0160: $gcd = gcdEuclidean($denominator, $numerator); //最大公約数
0161: $max = $denominator / $gcd; //約分した分母
0162:
0163: //分母に2, 5以外の素因数が含まれているかどうか
0164: $primes = array();
0165: primeDecomposition($max, $primes);
0166: $res = TRUE;
0167: foreach ($primes as $key=>$val) {
0168: if ($key != 2 && $key != 5 && $val > 0) {
0169: $res = FALSE;
0170: break;
0171: }
0172: }
0173: return $res;
0174: }
まず、分母と分子の最大公約数を求め、約分する。
次に、約分された分母の素因数分解を行い、分母に2または5以外の素因数が含まれているかどうかを調べる。
なお、分数で表せる無限小数は循環小数であることから、プログラムの結果は、「有限小数」「循環小数」のいずれかとなっている。
そこで今回は、分数の約分と素因数分解を駆使して、その分数が有限小数になるかどうか判定するプログラムを紹介する。「ユークリッドの互除法」「エラトステネスのふるい」といった定番アルゴリズムを使う。
（2021年2月17日）PHP8対応