写在前面的话： 我已经无数次用过这个函数了，但是每一次都不是很理解，总是忘了里面的原理，还是写下来记录一下吧.

算法过程描述：
取444个质数testtesttest：{2,3,5,7}\left \{ 2,3,5,7 \right \}{2,3,5,7}，设检测的数为ppp，并且设xxx为p−1p-1p−1。先将xxx表示成q∗2kq*2^{k}q∗2k（其中kkk为非负整数，qqq为奇数），然后∀i\forall i∀i，设定初始值aaa为(test[i])q(test[i])^{q}(test[i])q。每次计算aaa的平方(在模ppp运算下)tmptmptmp，如果tmptmptmp是111，那么aaa应该为111或者p−1p-1p−1，否则xxx为合数。将tmptmptmp赋值给aaa。∀i\forall i∀i，上述过程重复kkk次，最后aaa如果不是111,xxx为合数。

涉及定理：

1. 二次探测定理
   对上述过程的疑问1：
   \space\space\space\space    引自过程描述： 如果tmptmptmp是111，那么aaa应该为111或者p−1p-1p−1，否则xxx为合数。
   \space\space\space\space    证明： 由上述过程容易得： a2≡1modpa^2\equiv 1 \space mod\space pa2≡1 mod p，则应该有(a2−1)≡0modp(a^{2}-1)\equiv 0 \space mod\space p(a2−1)≡0 mod p。所以容易得到：p∣(a−1)(a+1)p|(a-1)(a+1)p∣(a−1)(a+1)。.进一步来看，a−1a-1a−1或a+1a+1a+1应该为ppp的倍数(在模ppp条件下，aaa为111或者p−1p-1p−1)，否则的话，(a−1a-1a−1)和(a+1a+1a+1)一定有两个因子或更多满足b1∗b2∗b3∗....=pb_{1}*b_{2}*b{3}*....=pb1​∗b2​∗b3∗....=p，则此时ppp不是素数。

2. 生成元定理
   对上述过程的疑问2：
   \space\space\space\space    引自过程描述： 最后aaa如果不是111,xxx为合数。
   \space\space\space\space    证明：由过程描述容易看出test[i]test[i]test[i]为素数，所以在modpmod\space pmod p的域中，test[i]test[i]test[i]为生成元，所以经过p−1p-1p−1次转动之后即(test[i])p−1(test[i])^{p-1}(test[i])p−1一定能转回到111.如果没转回来，说明modpmod\space pmod p不是域，也即ppp不是素数。这里扩展一下，在modpmod\space pmod p中，xxx的逆元为xp−2x^{p-2}xp−2，如果ppp较大，可以采用快速幂。

嗯，感觉现在懂了一点，放个代码吧，若您对我的描述有任何问题欢迎指出！

#include
typedef long long ll;
int pow(int a, int b, int p)
{int tmp = b;int k = 0;int sum = 1;while (b){if (b % 2 == 1){sum = ((ll)sum*a) % p;}a = ((ll)a*a) % p;b = b >> 1;}return sum;
}
int test[4] = { 2,3,5,7 };//这个test[i]做的是a，然后指数上是t
int rho(int x)
{int p = x;int k = 0;//for (int i = 0; i < 4; i++)//if (x == test[i])return 1;x--;while (!(x & 1)){x = x >> 1; k++;}for (int i = 0; i < 4; i++){//if (test[i] == p)return 1;if (test[i] == p)return 1;int a = pow(test[i], x, p);//这步很关键，做平方的时候是a的t次幂，不是a//同时有p=a^(t*2^k),这里，x=t,x已经被÷2处理过了int nxt=a;for (int j = 0; j < k; j++){nxt = ((ll)a*a) % p;if (nxt == 1 && a != 1 && a != p-1)return 0;a = nxt;}if (nxt != 1)return 0;}return 1;
}
int main(void)
{int n;scanf_s("%d", &n);int count = 0;for (int i = 2; i <= n; i++){//for(int j=0;j