素数判定（そすうはんてい）とは、ある自然数 "n" が素数であるか合成数であるかを判定する問題である。素数判定を行うアルゴリズムのことを素数判定法という。RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。仮定なしで決定的かつ多項式時間で終了する素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された（AKS素数判定法）。しかし多項式の次数が高く、実用上はAPR(Adleman-Pomerance-Rumely)判定法などのほうが高速であることが多い。なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。素数判定法の中には確率的アルゴリズムに基づいた、与えられた自然数 "n" を「合成数である」または「良く分からない」と判別する判定法がある。この判定法を確率的素数判定法（probabilistic primality test）ということがある。これに対して「素数である」あるいは否と判定する決定的アルゴリズムは決定的素数判定法（deterministic primality test）ということがある。「合成数である」と判定した場合には、"n"は合成数であると確定するが、「良く分からない」と判断した場合には、それだけではあまり有用な情報は得られない。しかし、判定を適当な回数だけ繰り返し、その間一度も「合成数である」と出力されないならば、その "n" は素数である見込みが大きいと言える。このようにして得られた「素数ではないかと思われる数」のことを確率的素数（probable prime）という。一般に確率的素数判定法は、決定的素数判定法よりもはるかに高速であるので、実用上は確率的素数判定法の繰り返しをもって素数判定法に代える場合も多い。また、Miller-Rabinの素数判定法はある種の一般化されたリーマン予想のもとでは多項式時間で動く素数判定法として動作することが知られている。C言語による素数判定（試し割り）のプログラム例を示す。入力nが素数である場合1が返り、それ以外の場合0が返る。Common Lispによる素数判定(エラトステネスの篩)のプログラム例を示す。入力nまでの素数のリストを返す。Schemeによる素数判定(エラトステネスの篩)のプログラム例を示す。入力nまでの素数のリストを返す。

出典:wikipedia