数論では、ルーカス・レーマー素数検定は、メルセンヌ数が素数かどうかを判定するための効率的な方法です。この記事では、PHP 言語と GMP 拡張機能 (GNU Multiple Precision Arithmetic Library、GNU Multiple Precision Math Library) を組み合わせて、Lucas-Lehmer 素数性テストを実装し、完全なコード例を提供します。
Lucas-Lehmer 素数性テストは、M = 2^n - 1 の形式のメルセンヌ数が素数であるかどうかを検出するために特別に設計されたアルゴリズムです。n は 1 より大きい正の整数です。このテストは、Lucas-Lehmer シーケンスに基づいています。数列の各要素を繰り返し計算し、最終的に数列の最後の要素が 0 であるかどうかを判断し、それによってメルセンヌ数の素数性を判断します。
PHP の組み込み関数は非常に大きな整数演算を処理できないため、GMP 拡張機能が必要です。 PHP をインストールするときに、GMP 拡張機能が有効になっているバージョンを選択することも、既存の環境で GMP 拡張機能を有効にすることもできます。
関数 lucasLehmerTest($n) { $s = '4'; $m = gmp_pow('2', $n) - '1'; for ($i = 1; $i < $n - 1; $i++) { $s = gmp_mod(gmp_pow($s, 2) - 2, $m); } if ($s == '0') { true を戻るします。 } false を戻るします。 }
分析:
関数では、gmp_pow を使用して 2 の $n$ マイナス 1 を計算して $m$ を取得し、$n-1$ 回繰り返して Lucas-Lehmer シーケンスを計算し、最後にシーケンスの最後の要素が 0 であるかどうかを判定して素数性を決定します。
$exponents = [2, 3, 5, 7, 13, 17]; foreach ($exponents として $exponent) { $result = lucasLehmerTest($exponent); if ($result) { echo "2^$exponent - 1 は素数です。"; } それ以外 { echo "2^$exponent - 1 は素数ではありません。"; } }
分析:
複数の指数値を含む配列 $exponents を定義し、foreach ループを使用して Lucas-Lehmer 素数性テスト関数を呼び出し、テスト結果に基づいた判定情報を出力します。
PHP および GMP 拡張機能を使用すると、Lucas-Lehmer 素数テストを簡単に実装し、大きな整数が素数かどうかを判断できます。大きなメルセンヌ数の素数判定には、Lucas-Lehmer アルゴリズムの方が効率的で、迅速に結果を得ることができます。この記事で提供されているコード例は、実用的なリファレンスとして使用できます。