定義檢測法王敏
根據素數定義：有A=n平方+b=(n-x)(n+y),若除n-x=1以外無正整數,則A為素數。
設A為代驗證數
求b=A-n平方 （b=<2n).
代入： y=(b+nx)/(n-x)（x<n-1)
若y無正整數解，則A為素數。
注意：x<n-1,而且n-x必為奇數，
例如：∵109=10×10+9
∴y=(9+10x)(10-x),只要計算當x=1,3,5,7時，y無正整數即可。經計算109是素數。
若y有正整數，則必為合數，
例如∵111=10^2+11,
當x=7時， y=(11+10×7) /(10-7)=27
∴A=(n-x)(n+y)=(10-7)(10+27)=3×37=111 不是素數。
此外，該不定方程還可找出一些特點，以提高計算速度。
詳見不定方程部分
確定型算法
試除法 嘗試從2到√N的整數是否整除N。 AKS 質數測試 PRIMES in P 這篇論文提到的方法，是第一個多項式時間的質數測試算法。
隨機算法
費馬測試 利用費馬小定理來測試。 Miller-Rabin 質數測試 歐拉-雅科比測試 對於N，挑選任意的M，測試（M/N）≡M^[(N-1)/2]。如果不成立，則N為合數。否則N有一半的機率是質數。
