[PHP] 数が”おそらく素数”であるかどうかを調べる関数 (gmp_prob_prime)

PHP数学, 素数

以前の記事で素数のチェック方法を書きました。

で、こんな関数が存在していることを初めて知りました。

PHP: gmp_prob_prime – Manual

gmp_prob_prime — 数が”おそらく素数”であるかどうかを調べる

数がおそらく素数であるかを調べるです。正確性はどうなんでしょう。

これがほぼ正確であればこちらを使えば自作の関数は不要ですね。

ということで検証。

gmp_prob_primeについて

説明

php.netによると、この関数は「Miller-Rabin の確率的テストを使用して、 その数が素数かどうかを調べます。」とあります。「ミラー–ラビン素数判定法」のことと思われます。これがどういったものかについては省略。

気になる方はハイパーリンクからWikipediaに飛んで確認してください。

書き方

gmp_prob_prime ( $a,$reps )

a

調べる数です。

reps

intを指定します。(省略可能)

php.netには「reps の合理的な値は 5 から 10 くらいまで変動します (デフォルトは 10 です)。より大きい値を指定すると、素数でない数を 「おそらく素数である」と誤認識する可能性が小さくなります。」と記載されています。

正直なところ、よくわかりません。

repsを10000にして以下のように調べてみましたが、結果は変わりませんでした。

$nums = range(1,1000000);
for($i=0;$i<count($nums);$i++) {
$res = gmp_prob_prime($nums[$i],10000);
}

返り値

以下のような数値を返します。

  • 0 – 確実に素数ではない
  • 1 – おそらく素数です。
  • 2 – 確実に素数です。

上記のように1000000までチェックしましたが、「おそらく素数です。」という結果は返りませんでした。repsを10000にしても同様です。

おそらく、少ない数だと1が返ることはないのでしょう。

返り値の検証

使い方が分かったところで、正しい結果が返されているかを検証してみたいと思います。

~1000000

1000000までの数で「2」を返す数字を配列に格納し、count関数で配列の個数をチェックします。

$primeNums = array();
$nums = range(1,1000000);
for($i=0;$i<count($nums);$i++) {
$res = gmp_prob_prime($nums[$i]);
if($res==2) {
$primeNums[] = $i;
}
}
echo count($primeNums);

結果は「78498」でした。別の方法で取得した結果と同じ結果です。

また内容についても同じでした。

結果をここに記載するとページが重くなってしまうので割愛します。

確認したい方はここからご覧ください。

1000000~

1000001~2000000までの数字で同様にチェックしたところ、「2 – 確実に素数です。」は０、「1 – おそらく素数です。」は70435でした。(repsはデフォルト値)

ということで、gmp_prob_prime関数は1000000までであれば、確実に素数判定に使用できそうです。それ以上の数は自作の関数でチェックがよさそうです。

PHP数学, 素数