•质数（prime number）又称素数，一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。 •1既不是质数又不是合数。
对于素数我们要了解其中一些有用的性质： 1.在N>3时，在任何的N和N+1之中必然有一个数不是质数 2.质数有无穷多个（反证法，p1p2p3…pn+1） 3.N和N+2都为素数的的情况有很多，这样的一对数素数叫做孪生素数（eg：3和5，5和7，11和13，1E9+7和1e9+9,孪生素数猜想:对所有自然数k，存在无穷多个素数对（p, p + 2）) 4.N以内的素数的个数随着N的增大趋近于logn 5.从不大于n的自然数随机选一个数，它是素数的概率大约是1/ln n （素数定理） 6.在一个大于1的数a和它的2倍之间（即区间(a, 2a]中）必存在至少一个素数。
对于素数，我们如果要判断是否是素数，则可以直接通过定义判断。
//思路：枚举2到2𝑛的所有的数，看能否整除n //时间复杂度：O（sqrt(n)） bool pd(int x){ bool flag=true; for(int i=2;i<=sqrt(x);i++){ if(x%i==0){ flag=false; break; } } return flag; }如果我们不只判断一个数，而是要打出素数表，应该怎么办呢。 如果直接枚举所有数直接判断，很明显时间复杂度O( n n n\sqrt{n} nn ),这个复杂度不是特别优秀。那我们应该怎么优化这个算法呢？
思路：要得到不大于某个自然数N的所有素数，只要在2—N中将不大于 n \sqrt{n} n 的素数的倍数全部划去即可。
//复杂度O(nloglogn) bool vis[maxn]; //vis[i]=true 即为素数 void primes(int n){ memset(vis,true,sizeof(vis)); vis[1]=false; for(int i=2;i<n;i++){ if(vis[i]){ if(i>n/i) continue;//防止i*i溢出 for(int j=i*i;j<n;j+=i){ vis[j]=false; } } } }