PHPで素数かどうか判定

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

(2023年4月1日)PHP8対応,"pahooInputData.php"導入

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

PHPで素数かどうか判定

サンプル・プログラム

圧縮ファイルの内容
isPrimeNumber.phpサンプル・プログラム本体。
pahooInputData.phpデータ入力に関わる関数群。
使い方は「数値入力とバリデーション」「文字入力とバリデーション」などを参照。include_path が通ったディレクトリに配置すること。
isPrimeNumber.php 更新履歴
バージョン 更新日 内容
1.1.0 2023/04/01 PHP8対応,"pahooInputData.php"導入
1.02 2020/01/25 エラーメッセージを変更
1.01 2020/01/19 number_format()を使わないようにした.扱える最大の自然数をMAX_INTEGERに変更.
1.0 2020/01/01 初版
pahooInputData.php 更新履歴
バージョン 更新日 内容
1.5.0 2024/01/28 exitIfExceedVersion() 追加
1.4.2 2024/01/28 exitIfLessVersion() メッセージ修正
1.4.1 2023/09/30 コメントの訂正
1.4.0 2023/09/09 $_GET, $_POST参照をfilter_input()関数に置換
1.3.0 2023/07/11 roundFloat() 追加

準備

  51: //Spinner - jQuery UI を使用するかどうか
  52: define('USESPINNER', TRUE);
  53: 
  54: //数値増減クリックで即判定するかどうか(TRUE:即判定,FALE:判定ボタンを用意)
  55: define('ONCHANGE', FALSE);
  56: 
  57: //ミラー・ラビン素数判定法を使うかどうか(高速判定できる)
  58: define('USE_MILLERRABIN', TRUE);
  59: 
  60: //表示幅
  61: define('WIDTH', 600);
  62: 
  63: //扱える最大の自然数
  64: 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

  66: /**
  67:  * 共通HTMLヘッダ
  68:  * @global string $HtmlHeader
  69: */
  70: $encode  = INTERNAL_ENCODING;
  71: $title   = TITLE;
  72: $width   = WIDTH;
  73: $int_max = MAX_INTEGER;
  74: 
  75: //数値変更、即判定
  76: if (ONCHANGE) {
  77:     $onchange =<<< EOT
  78: stop: function() { this.form.submit(this.form); }
  79: 
  80: EOT;
  81: else {
  82:     $onchange = '';
  83: }
  84: 
  85: //Spinner使用
  86: if (USESPINNER) {
  87:     $spinner =<<< EOT
  88: <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.10.2/jquery.min.js"></script>
  89: <script src="https://ajax.googleapis.com/ajax/libs/jqueryui/1.10.3/jquery-ui.min.js"></script>
  90: <link rel="stylesheet" href="https://ajax.googleapis.com/ajax/libs/jqueryui/1.10.3/themes/smoothness/jquery-ui.css" />
  91: <script>
  92: $(function() {
  93:     $('#number').spinner({
  94:         max: {$int_max},
  95:         min: 1,
  96:         step: 1,
  97:         {$onchange}
  98:     });
  99: });
 100: </script>
 101: 
 102: EOT;
 103: else {
 104:     $spinner = '';
 105: }
 106: 
 107: $HtmlHeader =<<< EOT

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

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

解説:単純素数判定法

 214: /**
 215:  * 単純素数判定法
 216:  * @param   int $n 判定する整数
 217:  * @return  bool TRUE:素数である/FALSE:素数でない
 218: */
 219: function PrimaryTest($n) {
 220:     //1は素数
 221:     if ($n == 1) {
 222:         $res = TRUE;
 223:     //2以上を調べる
 224:     } else {
 225:         for ($i = 2$i < $n$i++) {
 226:             if ($n % $i == 0) {
 227:                 $res = FALSE;
 228:                 break;
 229:             }
 230:         }
 231:         //自分自身なら素数
 232:         if ($i == $n) {
 233:             $res = TRUE;
 234:         }
 235:     }
 236:     return $res;
 237: }

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

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

解説:素数判定

 239: /**
 240:  * 素数判定
 241:  * @param   int $n 判定する整数
 242:  * @return  bool TRUE:素数である/FALSE:素数でない
 243: */
 244: function isPrimaryNumber($n) {
 245:     $res =  USE_MILLERRABIN ? MillerRabinPrimalityTest($n: PrimaryTest($n);
 246: 
 247:     return $res;
 248: }

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

補足:演算誤差について

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

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

活用例

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

参考サイト

(この項おわり)
header