质数筛选

1.埃式筛选法

从2开始向后枚举每个数的倍数,将其筛选去除,e.g:(2,3,4........p-1)若这个区间里没有任何一个数的倍数是p,则p一定是质数

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define ll long long
const int N=1e6+10;
using namespace std;
typedef pair<int,int>PII;

int cnt;
bool st[N];

void sieve_prime(int n){
    for(int i=2;i<=n;++i){
      if(!st[i]){
         cnt++;
         for(int j=i+i;j<=n;j+=i) st[j]=true;
      }
    }
}

int main(){
 ios::sync_with_stdio(false);
  int n;
   cin>>n;
    sieve_prime(n);

    printf("%d\n",cnt);
  return 0;
}

2.欧拉筛(线性筛)

 我们利用每个合数的最小质因数来进行筛选,i相当于是倍数,如果i%prime[j]==0，那么prime[j]一定是i*prime[j]这个合数的最小质因数,如果i%prime[j]!=0,那么prime[j]也同样还是这个合数的最小质因数(primep[j]比i的任何一个质因数都小)

2020/7/23日补:我们每次去找合数,都是用它的最小质因子来找的,那么我们要实现这个,就要求要在i%prime[j]=0的时候break,因为prime[j]一定是质数,所以它是i的质因子,那么我们再用i去找后面的合数之时,其最小质因子就会是我i%prime[j]=0,时的这个质数,而不是我们当前所枚举的这个质数.

这儿顺便附上一个:https://www.luogu.com.cn/problemnew/solution/P3383,这儿有更加详细的解释

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e8 + 10;
const int M = 1e9 + 7;
using namespace std;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
int n,q,k;
int prime[N],cnt;
bool st[N];

void get_prime(int n){
    for(int i=2;i<=n;++i){
        if(!st[i]) prime[cnt++]=i;
         for(int j=0;j<cnt && prime[j]<=n/i;++j){
             st[i*prime[j]]=true;    //一定能保证prime[j]是i*prime[j]的因数
             if(i%prime[j]==0) break;
         }
    }
}

int main() {
    ios::sync_with_stdio(false);
   cin>>n>>q;
   get_prime(n);
    while(q--){
        cin>>k;
         printf("%d\n",prime[k-1]);
    }
    return 0;
}