根据素数定义:有A=n平方+b=(n-x)(n+y),若除n-x=1以外无正整数,则A为素数.设A为代验证数求b=A-n平方(b=<2n).代入:y=(b+nx)/(n-x)(x若y无正整数解,则A为素数.注意: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不是素数.此外,该不定方程还可找出一些特点,以提高计算速度.详见不定方程部分.根据素数定义:有A=n平方+b=(n-x)(n+y),若除n-x=1以外无正整数,则A为素数. 设A为代验证数 求b=A-n平方(b=2n). 代入:y=(b+nx)(n-x)(x 若y无正整数解,则A为素数. 注意: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质数测试PRIMESinP这篇论文提到的方法,是第一个多项式时间的质数测试算法. 费马测试利用费马小定理来测试.Miller-Rabin质数测试欧拉-雅科比测试对于N,挑选任意的M,测试(MN)≡M^[(N-1)2].如果不成立,则N为合数.否则N有一半的机率是质数.