题目描述

给定一个正整数 n，请你求出 1∼n中质数的个数。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示 1∼n中质数的个数。
数据范围
1≤n≤$10^6$

样例

输入样例：
8
输出样例：
4

算法1 埃氏筛

$O(nloglogn)$

算法核心:把i的倍数（在n的范围内）统统筛掉，没被筛掉就是质数

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int primes[N],cnt;
bool st[N];
void get_primes(int n){ //朴素筛 
    for(int i=2;i<=n;i++){
        if(st[i]) continue; //i不是质数 
        primes[cnt++]=i;  //记下质数 
        for(int j=i+i;j<=n;j+=i){ //把i的倍数（在n的范围内）统统标记（删去） 
            st[j]=1;
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    get_primes(n);
    printf("%d\n",cnt);
    return 0;
}

算法2 线性筛（欧拉筛）

(暴力枚举) $O(n)$

算法核心：x仅会被其最小质因子筛去
1.对于合数x是否被筛掉，一定会被筛掉
2.假设pj是x的最小质因子，当i循环到x/pj的时候，就会被筛掉
这也就是内层循环，写的是;primes[j]<=n/i，的原因。把i和pj移项，就会出现i<=n/pj
3.对于循环里面if的判断，若i%pj==0，那说明pj是i的最小质因子，因为pj是从小到大遍历的，之前没被整除，说明都不是因子
pj是i的最小质因子，那pj一定也是i*pj的最小质因子，因为i整除pj，pj整除pj，如果有更小的质因子，那就与pj是i的最小质因子的结论相矛盾
然后break掉，因为再往后遍历pj，就会出现不是最下的质因子
4.如果i%pj!=0，那么pj比i所有因子还小，所以pj也为pj*i最小质因子
所以，上面的数都会因为上面的操作，会1——n的范围内的数，合数都会被被最小质因子筛掉

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int primes[N],cnt;
bool st[N];
void get_primes(int n){   //欧拉筛(线性筛)
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i; //存没被筛掉的数（质数）
        for(int j=0;primes[j]<=n/i;j++){ 
            st[primes[j]*i]=1;
            if(i%primes[j]==0) break;  
        }                        
    }          
}
int main(){
    int n;
    scanf("%d",&n);
    get_primes(n);
    printf("%d\n",cnt);
    return 0;
}