质数（prime）又称素数，指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。与之相反的是合数。
性质
- 有无数个
- $\cdots
判断方法
- 从定义出发，设i=2~n-1,逐个枚举i，若i整除n，则说明n有除了1和它本身之外的因数，不是质数。
1 inline bool is_prime1(int x) { 2 if(n == 1) return false; 3 for(register int i = 2; i < n; ++i) { 4 if(x % i == 0) return false; 5 return true; 6 } 7 }
时间复杂度$O(n)$
- 我们很容易得出，若i是n的因子，那么$\frac{n}{i}$也是n的一个因子，反正i不是n的因子，那么$\frac{n}{i}$也不是n的因子。所以我们只要判断1到$\sqrt{n}$的数是不是存在n的因子即可。
inline bool is_prime2(int x) { if(x <= 1) return false; int t = sqrt(x); for(register int i = 2; i <= t;++i) if(x % i == 0) return false; return true; }
时间复杂度$O(\sqrt{n}）$ 这已经足以满足在正常算法竞赛的使用了
- 对于任意一个自然数，都可以把它表示为 6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5 $x\ge 1且x为整数$.
6x+2=2（3x+1） 6x+3=3(2x+1) 6x+4=2(3x+2) 所以可以表示为这三个数的数字一定不是质数. 而6x+5 可以表示为6(x+1) -1
所以我们可以发现，素数一定会在6的倍数的两侧，相差为1，这也是孪生素数的定义
inline bool is_prime3(int x ) { if(x == 2 || x == 3 )return 1 ;//特判 if(x % 6 != 1 && x % 6 != 5)//其他三种情况一定不是质数 return false ; int t = sqrt(x); for(register int i = 5; i <= t; i += 6 ) if(x % i == 0 || x % (i + 2) == 0 ) return false ;//在6x两侧也不一定是素数，要检验一下 return true; }
时间复杂度$O（\frac{\sqrt{n} }{3})$ 这里稍作解释,大O表示算法时间复杂度上界，上文的代码循环的if语句最多要判断两次，所以要×2。 这已经十分优秀了
-
Pollard-Rho算法
当n十分大的时候，上述三种算法就统统TLE了，那么有没有什么算法可以更高效，准确的判断呢？如果是常数级的更好了。
其实是没有的。。。。
将介绍的是Pollard-Rho算法，是一种随机算法（看RP？）
看下面的代码
- 跑素数筛，列出素数表，就很好判断是不是素数了。