素数的定义：除了1和它本身之外，不能被其他整数整除。
一、判定一个正整数n是否为素数的方法：
①定义法：枚举2~n-1这n-2个正整数，如果它们均不能整除n，则可断定n为素数。代码如下：时间复杂度为O(n)，如果n为10^9，就不能用此方法。
1 bool is_prime(int n){ 2 if(n==1)return false; 3 for(int i=2;i<n;++i) 4 if(n%i==0)return false; 5 return true; 6 }
②从2开始枚举到不大于sqrt(n)的所有正整数，如果它们均不能整除n，则可断定n为素数。为什么只需枚举到sqrt(n)就可以了呢？理由：假设n存在大于或等于sqrt(n)的因子y，则z=n/y必同时为n的因子，且其值小于或等于sqrt(n)（如果z>sqrt(n)，那么z*y>n与n=z*y相矛盾）。所以，若n存在相异于1和它本身的因子y>sqrt(n)，则必存在小于或等于sqrt(n)的因子，因此，我们只需测试因子到sqrt(n)即可。时间复杂度为O(sqrt(n))。
1 bool is_prime(int n){ 2 if(n==1)return false; 3 for(int i=2;i*i<=n;++i) 4 if(n%i==0)return false; 5 return true; 6 }
二、给定一个正整数n(n<=10^6)，问n以内有多少个素数？如果采用方法2，时间复杂度最坏能达到1e9!!!超时是毫无疑问的，那么是否有比较快速的判断方法呢？于是两种经典筛法就呼啦呼啦地闪亮登场了。
①埃氏筛法：要得到自然数n以内的全部素数，必须把不大于sqrt(n)的所有素数的倍数剔除，剩下的都是素数。时间复杂度只有O(nloglogn)，非常接近O（n）。方法：最小的素数是2，先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......最后剩下的一定是素数，根据定义，下面给出埃氏筛的两种写法：一种是直接判定素数，另一种是边判定素数边保存素数，代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1000; 4 bool isp[maxn];int cnt=0,prime[maxn]; 5 void sieve1(){//1、直接判定素数 6 memset(isp,true,sizeof(isp)); 7 isp[0]=isp[1]=false; 8 for(int i=2;i*i<maxn;++i){ 9 if(isp[i]){ 10 for(int j=i*i;j<maxn;j+=i) 11 isp[j]=false; 12 } 13 } 14 } 15 void sieve2(){//2、边判定素数边保存素数 16 memset(isp,true,sizeof(isp)); 17 memset(prime,0,sizeof(prime)); 18 isp[0]=isp[1]=false; 19 for(int i=2;i<maxn;++i){ 20 if(isp[i]){//如果isp[i]==true，则i一定是素数 21 prime[cnt++]=i;//保存素数 22 for(int j=i*i;j<maxn;j+=i) 23 isp[j]=false; 24 } 25 } 26 } 27 int main(){ 28 sieve1();//测试代码 29 for(int i=1;i<maxn;++i) 30 if(isp[i])cout<<i<<endl; 31 /*sieve2(); 32 for(int i=0;i<cnt;++i) 33 cout<<prime[i]<<endl;*/ 34 return 0; 35 }
疑点一：根据埃氏筛的定义，只需枚举不大于sqrt(n)内的所有素数，将其倍数剔除掉，最终留下的都是素数，为什么只需枚举到sqrt(n)呢？原因是任何一个合数至少有一个不大于sqrt(n)的最小素因子，我们可以通过这个最小素因子来筛掉这个合数。
疑点二：第二重循环为什么不是从j=2*i或者是j=k*i(k<i)开始以增量i向上筛掉合数？因为k<i，如果k是素数，那么k*i在之前早就被筛掉了；如果k是合数，同理k*i至少已被前面某个较小素的因子给筛掉了，所以j从i*i开始向上枚举。尽管这样，埃氏筛法避免不了重复筛掉元素这个多余的操作。最后注意一下，第二种方法中第一重循环i要小于maxn，因为要保存maxn内的所有素数嘛，如果还是i*i<maxn，那么保存的只是sqrt(n)内的所有素数而已。现在问：如果要求1e7内所有的素数，那么仍采用埃氏筛法？恐怕有点不太好卡时间······一般会超时，而欧拉筛可以把时间卡得刚刚好，时间复杂度是O(n)，即保证了每个合数只被筛掉一次。期待地搓搓小手，欧拉筛（线性筛）终于压轴出场了......先上一下模板代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1000; 4 bool isp[maxn];int cnt=0,prime[maxn]; 5 void euler_sieve(){ 6 memset(isp,true,sizeof(isp)); 7 memset(prime,0,sizeof(prime)); 8 isp[0]=isp[1]=false; 9 for(int i=2;i<maxn;++i){ 10 if(isp[i])prime[cnt++]=i; 11 for(int j=0;j<cnt&&i*prime[j]<maxn;++j){ 12 isp[i*prime[j]]=false; 13 if(i%prime[j]==0)break;//这一步巧妙地保证了每个合数都被其最小素因子只筛掉一次 14 } 15 } 16 } 17 int main(){ 18 //测试代码： 19 euler_sieve(); 20 for(int i=0;i<cnt;++i) 21 cout<<prime[i]<<endl; 22 return 0; 23 }
②欧拉筛法：任何一个合数都可以写成几个质数相乘的形式，也就是任何一个合数至少有一个最小质因子，而每一个质数的倍数一定不是质数，所以我们可以通过每一个合数的一个最小素因子去筛掉它，并且只筛掉一次，这样就把时间复杂度降到了O(n)。其中就是这条语句起着至关重要的作用：if(i%prime[j]==0)break;为什么呢？举个栗子：假设当前i=9，prime素数表里有2，3，5，7，即先筛掉2*9=18，然后筛掉3*9=27，判断9%3==0，退出当前循环。因为9=3*3，如果继续筛掉5*9，相当于筛3*3*5=3*15，而这个数在i=15时筛掉就可以了。因此，可以用以下的推导证明上面的结论：假设pi是当前i的最小质因子，那么素数表有p1<p2<...<pi<pi+1<...，枚举当前质数表p[j]，j从小到大枚举，直到i%p[j]==0这个条件时，前面所有质数p[j]都是i*p[j]的最小质因子，如果继续枚举下去，即下一个要被筛掉的合数为i*prime[j+1]，因为i中已经含有一个最小质因子prime[j]，设i=k*prime[j]，则i*prime[j+1]=k*prime[j]*prime[j+1]=k'*prime[j]，显然k'>i，k'*prime[j]可以留在后面被筛掉。换句话说，prime[j+1]已不是i*prime[j+1]的最小质因子，i*prime[j+1]必然可以被一个更小的质数prime[j]筛掉，那么k'=i*prime[j+1]/prime[j]=k*prime[j+1]就一定比i大，即下一次i遍历到i=k'时，k'*prime[j]却被其最小素因子prime[j]筛掉，而不是prime[j+1]，这就相当于再筛选了一次（增加了时间复杂度），所以只需将j遍历到i的最小素因子prime[j]就可以了，即保证每一个合数只被其最小质因子筛掉，这样把时间复杂度完美地从O(nloglogn)降到了O(n)。