PHPで素数かどうか判定

(1/1)
PHP で素数日を列挙」では、PHP で素数日を列挙するプログラムを作ったが、今回は入力した整数が素数かどうかを判定するプログラムを作ってみる。
デフォルトの入力値は現在の年月日、入力 UI には jQuery UISpinner を利用できるようにする。また、素数判定方式として、単純素数判定法とミラー・ラビン素数判定法の 2種類から選択できるようにする。

(2020 年 1 月 19 日)number_format()を使わないようにした。扱える最大の自然数を MAX_INTEGER に変更した。

サンプル・プログラムの実行例

PHPで素数かどうか判定

サンプル・プログラム

圧縮ファイルの内容
isPrimeNumber.phpサンプル・プログラム本体。

準備

0030: //Spinner - jQuery UI を使用するかどうか
0031: define('USESPINNER', TRUE);
0032: 
0033: //数値増減クリックで即判定するかどうか(TRUE:即判定,FALE:判定ボタンを用意)
0034: define('ONCHANGE', FALSE);
0035: 
0036: //ミラー・ラビン素数判定法を使うかどうか(高速判定できる)
0037: define('USE_MILLERRABIN', TRUE);
0038: 
0039: //表示幅
0040: define('WIDTH', 500);
0041: 
0042: //扱える最大の自然数
0043: define('MAX_INTEGER', pow(2, 48)); //参考:倍精度浮動小数の仮数部は52bit

定数 USESPINNERONCHANGEUSE_MILLERRABIN は、必要に応じて TRUEFALSE のいずれかの値を設定する。

jQuery UI を使いたくないページでは、USESPINNERFALSE にする。
jQuery UISpinner で数値を増減させ、すぐに判定を行いたい場合は ONCHANGETRUE にすればいいが、1 だけ増減する度に PHP プログラムが走るので、サーバ負荷を軽減する目的で FALSE にしてもよい。
PHP と Python で巨大素数を扱う」で紹介したミラー・ラビン素数判定法 は高速で素数判定を行うことが出来るので、ONCHANGETRUE にしたときは、USE_MILLERRABINTRUE にするといいだろう。

定数 MAX_INTEGER は、扱える最大の自然数を 2 のべき乗で表現している。詳しくは「補足:演算誤差について」を参照。

解説:Spinner - jQuery UI

0045: /**
0046:  * 共通HTMLヘッダ
0047:  * @global string $HtmlHeader
0048: */
0049: $encode  = INTERNAL_ENCODING;
0050: $title   = TITLE;
0051: $int_max = MAX_INTEGER;
0052: 
0053: //数値変更、即判定
0054: if (ONCHANGE) {
0055: $onchange =<<< EOD
0056: stop: function() { this.form.submit(this.form); }
0057: 
0058: EOD;
0059: else {
0060:     $onchange = '';
0061: }
0062: 
0063: //Spinner使用
0064: if (USESPINNER) {
0065: $spinner =<<< EOD
0066: <script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/jquery/1.10.2/jquery.min.js"></script>
0067: <script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/jqueryui/1.10.3/jquery-ui.min.js"></script>
0068: <link type="text/css" rel="stylesheet" href="https://ajax.googleapis.com/ajax/libs/jqueryui/1.10.3/themes/smoothness/jquery-ui.css" />
0069: <script type="text/javascript">
0070: $(function() {
0071:     $('#number').spinner({
0072:         max: {$int_max},
0073:         min: 1,
0074:         step: 1,
0075:         {$onchange}
0076:     });
0077: });
0078: </script>
0079: 
0080: EOD;
0081: else {
0082:     $spinner = '';
0083: }
0084: 
0085: $HtmlHeader =<<< EOD

Spinner - jQuery UIは、Google Hosted Libraries のものを呼び出している。

プロパティとして、入力最大値 max に PHP で扱える最大整数 PHP_INT_MAX を設定する。この最大整数は PHP 処理系によって異なるので、ご留意いただきたい。

解説:単純素数判定法

0218: /**
0219:  * 単純素数判定法
0220:  * @param int $n 判定する整数
0221:  * @return bool TRUE:素数である/FALSE:素数でない
0222: */
0223: function PrimaryTest($n) {
0224:     //1は素数
0225:     if ($n == 1) {
0226:         $res = TRUE;
0227:     //2以上を調べる
0228:     } else {
0229:         for ($i = 2; $i < $n$i++) {
0230:             if ($n % $i == 0) {
0231:                 $res = FALSE;
0232:                 break;
0233:             }
0234:         }
0235:         //自分自身なら素数
0236:         if ($i == $n) {
0237:             $res = TRUE;
0238:         }
0239:     }
0240:     return $res;
0241: }

ユーザー関数 PrimaryTest は、素数の定義に則り、与えられた整数が素数かどうかを判定する。

$n が 1 なら素数である。
2 以上$n 未満の整数で除算を繰り返し行い、もし剰余がゼロになったら素数ではない。
以上の計算を行った上で、$n自身が残れば、素数である。

解説:素数判定

0243: /**
0244:  * 素数判定
0245:  * @param int $n 判定する整数
0246:  * @return bool TRUE:素数である/FALSE:素数でない
0247: */
0248: function isPrimaryNumber($n) {
0249:     $res =  USE_MILLERRABIN ? MillerRabinPrimalityTest($n) : PrimaryTest($n);
0250: 
0251:     return $res;
0252: }

ユーザー関数 isPrimaryNumber は、定数 USE_MILLERRABINTRUE ならミラー・ラビン素数判定法を、そうでなければ上述の単純素数判定法を実行する。

補足:演算誤差について

組み込み関数  number_format  は第一引数が float 型であるため、仮数部は 52 ビットである。一方、PHP 処理系で扱える最大の自然数 PHP_INT_MAX は 64 ビットである処理系が多いため、52 ビットを超えると、関数 number_format で正しく変換されないことがある。
当初、ヘルプ等で関数 number_format を使っていたが、これを省くようにした。

同様に、素数判定の際、内部処理で float 型にキャストするため、52 ビットを超える自然数では誤差が発生する。そこで、扱える最大の自然数を定数 MAX_INTEGER で制限するようにした。デフォルト値は 48 ビットである。

活用例

みんなの知識 ちょっと便利帳では、「きょうは素数日? & 素数を判別」のコーナーで、このサンプル・プログラムを活用している。ありがとうございます。

参考サイト

(この項おわり)
header