质数筛选总结_埃氏筛法、欧拉筛法

概述

质数：只有两个正因数（1和它本身）的自然数即为质数。

合数：比1大但不是质数的数称为合数。

1和0既非质数也非合数。

问题描述：求 1,2,⋯ , N中素数的个数。

**输入：**一行一个整数 N。

**输出：**一行一个整数，表示素数的个数

1 试除法

给定的整数n，除以1<i<n的数，如果都不能整除，则n为质数。10个测试用例全部超时。

#include <bits/stdc++.h>
using namespace std;
int n ,sum=0,flag=0;
int main(){
 cin >> n;
 for(int i=2;i<=n;i++)
 {
  flag=0;
  for(int j=2;j<i;j++)
  {
   if (i%j==0)
   {
    flag=1;
   }
  }
  if(flag==0)
  {
   sum++;
  }
  
 }
 cout <<sum;
 return 0;
}

2 试除法优化

对于所有的整数，因数是成对出现的a*b=n，当a,b无限接近时a<= sqrt(n)。因此，枚举范围可以缩小至2~sqrt(n)。10个测试用例通过2个,其它超时。

#include <bits/stdc++.h>
using namespace std;
int n ,sum=0,flag=0;
int main(){
 cin >> n;
 
 for(int i=2;i<=n;i++)
 {
  flag=0;
  for(int j=2;j<=sqrt(i);j++)
  {
   if (i%j==0)
   {
    flag=1;
   }
  }
  if(flag==0)
  {
   sum+=1;
  
  }
 }
 cout <<sum;
 return 0;
}

3 埃氏筛法

埃氏筛法对多个整数进行质数判断时，算法更优。原理首先找出最小的素数2，把2的倍数都标记为合数，然后再找下一个没有被标记为合数的数3，把3的倍数标记为合数，依次类推。假设多个整数中的最大值为20，算法实现过程：

1. 遍历2~20所有整数数组a[i] (2<=i<=20)，默认值a[i]=1;
2. 最小整数i=2是质数，所有2的倍数均为不是质数，都划掉a[i]=0；
3. i=3，如果a[3]=1,所有3的倍数均不是质数，都划掉a[i]=1；
4. i=4，因为a[4]=0，4不是质数，继续下一个
5. i=5，以为a[5]=1,所有5的倍数均不是质数，都划掉a[i]=1;
6. 最后，剩余的a[i]=0的数，均为质数。

10个测试用例通过8个,其它超时

#include <bits/stdc++.h>
using namespace std;
int n ,sum=0,a[100000001];//a[i]=0是素数，a[i]=1不是素数。 

int main(){
 cin >> n;
 a[1]=1;
 for(int i=2;i<=n;i++)
 {
  if(a[i]==0)
  {
   for(int j=2;j<=n;j++)
   {
    if(i*j>n) break;
    a[i*j]=1;
   }
  }
  
 }
 for(int i=2;i<=n;i++)
 {
  if(a[i]==0)
  {
   sum++;
  }
 }
 cout <<sum;
 return 0;
}

4 欧拉筛法

欧拉筛法是在埃式筛法的基础做了改进。埃氏筛法中一个合数可能会被筛多次，如6可以被2筛去也可以被3筛去，而欧拉筛法是让每个合数只被它的最小质因子筛选一次。

创建一个额外数组prime存储素数，然后从2开始依次遍历2~n区间内的数：

i=2时：

判断素数：a[2]未被标记为合数=>a[2]=true标记为素数，prime数组增加一个素数。prime[0]=0 ，++prime[0] 后，prime[0]=1,prime[1]=2;

判断合数：遍历prime数组的所有素数

j=1时a[prime[1]*2]=a[4]=true;

i=3时：

判断素数：a[3]未被标记为合数=>a[3]=true标记为素数，prime数组增加一个素数。prime[0]=1 ，++prime[0] 后，prime[0]=2,prime[2]=3;

判断合数：遍历prime数组的所有素数

j=1时，a[prime[1]*3]=a[6]=true;

j=2时，a[prime[2]*3]=a[9]=true;

因为 3%prime[2]=3%3=0，所以跳出循环。

i=4时，

判断素数：a[4]被标记为合数，prime数组不增加；

判断合数：遍历prime数组的所有素数

j=1时，a[prime[1]*4]=a[8]=true;

因为 4%prime[1]=4%2=0，所以跳出循环。

注：如果不跳出循环,因为i%prime[j]=0，故i=t倍prime[j]，所以i*prime[j+1]=t * prime[j] * prime[j+1]，即当j=2时： prime[2]*4=2*prime[1]*prime[2] =12；相当于prime[j]的倍数已经标记，prime[j+1]就是重复标记了。

10个测试用例全部通过

#include <bits/stdc++.h>
using namespace std;
int n ,sum=0,prime[1000000];
bool a[100000001];//a[i]=0没有访问过，1访问过。prime存素数 
int main(){
 cin >> n;
 memset(prime,0,sizeof(prime));
 memset(a,0,sizeof(a));
 a[1]=1;
 for(int i=2;i<=n;i++)
 {
  if(!a[i]) // 没有被标记为合数 
  {
   a[i]=true;
   //i=2时，prime[0]=0 ，++prime[0] 后，prime[0]=1,prime[1]=2; 
   //i=3时，prime[0]=1 ，++prime[0] 后，prime[0]=2,prime[2]=3;
   //i=5时，prime[0]=2 ，++prime[0] 后，prime[0]=3,prime[3]=5; 
   prime[++prime[0]]=i; 
    
  }
  for(int j=1 ;j<=prime[0] && i*prime[j]<=n;j++)
  {
   a[prime[j]*i]=true;//合数
   if(i%prime[j]==0) break; 
  }
  
 }
 cout <<prime[0];
 return 0;
}