「合成数である」と判定した場合には、nは合成数であると確定するが、「良く分からない」と判断した場合には、それだけではあまり有用な情報は得られない。素数である見込みが大きいと言える。はるかに高速であるので、実用上は確率的素数判定法の繰り返しをもって素数判定法に代える場合も多い。ミラー–ラビン素数判定法はある種の一般化されたリーマン予想のもとでは多項式時間で動く素数判定法として動作することが知られている。多項式時間アルゴリズムだが、GRHのもとで正当性が示される。高速だが、多項式時間アルゴリズムではない。フェルマー数に対する判定法プログラム例[編集]Pythonによる素数判定(試し割り)のプログラム例を示す。Trueこの例は入力nが素数である場合はTrueを返し、それ以外の場合はFalseを返す。Pythonによる素数判定(エラトステネスの篩)のプログラム例を示す。list_primeこの例は入力nまでの素数のリストを返す。(日時は個人設定で未設定ならばUTC)。表示-継承ライセンスの下で利用可能です。追加の条件が適用される場合があります。詳細は利用規約を参照してください。Cookieに関する声明モバイルビュ。