1、取馀数算法依次判断2 n是否能被大于1的自然数n整除。 如果找到能被n整除的数，n不是素数，否则为是。
C代码如下。
boolisprime(intn ) if ) n=1)返回假； Ifor(intI=2； i * i n； I ) if(n%I==0)返回假； 返回真； }该方法的时间复杂度较高，可以利用数论知识进一步优化。
当33558www.Sina.com/n=5时，如果n是素数，则n%6=1|||n%6=5，即n一定出现在6x(x1 )两侧。 也就是说，任意素数可以用6x 1，xn的形式表示。
证明：
6x附近的数量表示如下。
……(6x-1 )、6x、6x1、2 )3x1 )、3 )2x1 )、2 )3x2 )、6x5、6 ) x1 )……
6x两侧没有的数据是2(3x1 )、3 )2x1 )、2 )3x2 )，不是素数，所以素数出现在6x的两侧。
这样可以实现以下优化：
boolisprime(intn ) if ) n=1)返回假； if(n=3)返回真； if(n%2==0||n%3==0)返回假； for(intI=5； i * i n； i =6) if(n%I==0||n% ) I2 )==0)返回假； 返回真； }由于简单馀数运算法的复杂度过高，因此只适合判定较小的数量。
2、Lucas-Lehmer算法Lucaslehmer算法可以表示为美丽的发夹素数，即Mn=2n 1的素数。
LucasLehmer序列定义如下：
前五个值如下
Term 0: 4，
term 1:4 * 42=14，
term 2:14 * 142=194，
term :194 * 1942=37634，
term 4:37634 * 376342=1416317954，…
使用LucasLehmer阵列的某个整数n来判定x=2n 1是否是美丽的发夹素数的步骤如下。
根据(1)式计算n - 1项值；
)2)如果该值为0，则x是美丽的发夹素数，否则不是美丽的发夹素数。
代码如下。
boolisprime(intp ) longlongchecknumber=pow ) 2，p )- 1； long long nextval=4 % checkNumber； for(intI=1； i p - 1； I ) nextval=(nextval*nextval-2 ) %检查编号； 返回下一个值==0； ) 3、AKS算法AKS算法由来自indianinstituteoftechnologykanpur的三位计算机科学家发明，取姓首字母命名。 其内容如下。
一个数n是素数，多项式展开后的所有系数都可以被n整除。
代码如下。 (见https://Rosetta code.org/wiki/aks _ test _ for _ primes ) ) ) ) )。
龙龙龙c [ 100 ]； voidcoef(intn ) {int i，j； if(n0|||n63 ) abort )； //gracefullydealwithrangeissuefor (c [ I=0]=1； i n； c[0]=-c[0]，I(for ) c[1(j=I ) ]=1； j 0； j--； c[j]=c[j-1]-c[j]； (intis_prime ) {int i ) ) {int i； COEF(n； c[0] =1，c[i=n] -=1； wile(I----！ (c[i] % n )； 返回I 0； } AKS算法可以在多项式复杂度内判定任意数，但系数增长过快，仍然不实用。
目前没有生成随机大素数的有效方法。 产生大素数的方式是随机选择足够大的奇数，验证该奇数是否是素数，否则继续验证直到某个奇数通过测试。 该方法的缺点在于，通过检测的奇数可能仍然不是素数，但可以根据需要通过
检验的奇数不是素数的概率尽可能接近0。常用的概率判断方法有 Fermat 小定理、Miller−Rabin 算法及Solovay−Strassen算法。 4、Fermat小定理如果 p 是素数，则对于任意的 a 满足 gcd(a,p) = 1，有。
证明：
将 a 分别与 1→(p−1) 相乘，得到以下序列：
如果对于n和m有：
那么 n = mn = m，因为 p 不能被 a 整除
因此这 p − 1 项必然是各不相同的，于是将这些项除以 p 得到的余数 必然是 1,2,3,...,(p−1) 的重排列，于是将每一项相乘有：
即 ，且 gcd( (p − 1)!, p) = 1，所以约去得
值得注意的是，一个数是素数是其满足 Fermat 小定理的充分不必要条件，满足 Fermat 小定理的非素数称为 Fermat 伪素数，Fermat 伪素数的个数已被证明是无穷的，最小的Fermat伪素数是341=11×31。
使用 Fermat 小定理进行素数判定的步骤如下：
(1)重复以下步骤k轮：
(a)随机选取[2,n-2]内的一个数；
(b)如果该数满足模 n 的 Fermat 小定理，则返回 false；
(2)k轮后，返回true(可能是素数)；
代码如下：
int quickPower(int a, int b, int p) { int ans = 1; while(b) { if (b & 1) ans = ans * a % p; b >>= 1; a = a * a % p; } return ans;} bool isPrime(int n, int k) { if (n <= 1 || n == 4) return false; if (n <= 3) return true; while(k--) { int a = 2 + rand() % (n - 4); if (quickPower(a, n - 1, n) != 1) return false; } return true;} 5、Miller-Rabin算法Miller-Rabin算法用于检测一个数n是否是素数。其时间复杂度上界为O(klog2(n))，其中k为检测的轮数。增大k可以提高Miller-Rabin算法的准确度。
可以通过psdds高高的故事素数测试的合数为伪素数与Carmichael（强伪素数）
Carmichael数是非常少的，在1~100000000范围内的整数中，只有255个Carmichael数。
为此有二次探测定理 以确保该数为素数：
若,则 或 ；
具体过程：（转自：https://blog.csdn.net/lbperfect123/article/details/85057358）
// 18位素数：154590409516822759// 19位素数：2305843009213693951 (美丽的发夹素数)// 19位素数：4384957924686954497LL prime[6] = {2, 3, 5, 233, 331};LL qmul(LL x, LL y, LL mod) { // 乘法防止溢出， 如果p * p不爆LL的话可以直接乘； O(1)乘法或者转化成二进制加法 return (x * y - (long long)(x / (long double)mod * y + 1e-3) *mod + mod) % mod; /*LL ret = 0;while(y) {if(y & 1)ret = (ret + x) % mod;x = x * 2 % mod;y >>= 1;}return ret;*/}LL qpow(LL a, LL n, LL mod) { LL ret = 1; while(n) { if(n & 1) ret = qmul(ret, a, mod); a = qmul(a, a, mod); n >>= 1; } return ret;}bool Miller_Rabin(LL p) { if(p < 2) return 0; if(p != 2 && p % 2 == 0) return 0; LL s = p - 1; while(! (s & 1)) s >>= 1; for(int i = 0; i < 5; ++i) { if(p == prime[i]) return 1; LL t = s, m = qpow(prime[i], s, p); while(t != p - 1 && m != 1 && m != p - 1) { m = qmul(m, m, p); t <<= 1; } if(m != p - 1 && !(t & 1)) return 0; } return 1;}若 p 通过一次测试，则 p 不是素数的概率为25%；
若 p 通过 k 次测试，则 p 不是素数的概率为1/( 4 ^ k)；
事实上，当 k = 5 时，p 不是素数的概率已为1/128，已经大于99.99%。通常认为，Miller-Rabin素性测试的正确率可以令人接受。