[PHP] 数が”おそらく素数”であるかどうかを調べる関数 (gmp_prob_prime)
以前の記事で素数のチェック方法を書きました。
で、こんな関数が存在していることを初めて知りました。
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 – 確実に素数です。」は0、「1 – おそらく素数です。」は70435でした。(repsはデフォルト値)
ということで、gmp_prob_prime関数は1000000までであれば、確実に素数判定に使用できそうです。それ以上の数は自作の関数でチェックがよさそうです。
ディスカッション
コメント一覧
まだ、コメントがありません