题目内容

给定一个正整数n，请你求出1~n中质数的个数。

输入格式

共一行，包含整数n。

输出格式

共一行，包含一个整数，表示1~n中质数的个数。

数据范围

1≤n≤10^6

输入样例

8

输出样例

4

题解

埃氏筛法：
以前方的数为基础，删掉可以整除的后方的数。将全部的数过滤完之后，剩余的就是质数。比如：2，3，4，5，6，7，8，9，10，11，12，13，14。跟据2，把4，6，8，10，12，14删除；跟据3，把6，9，12删除；跟据4，把8，12删除；依此类推。

线性筛法：
n只会被最小质因子筛掉
1、i % primes[j] == 0
primes[j] 一定是i的最小质因子，primes[j]一定是primes[j] i的最小质因子
2、i % primes[j] != 0
primes[j]一定小于i的所有质因子，primes[j]也一定是primes[j] i的最小质因子
对于一个合数x，假设primes[j]是x的最小质因子，当i枚举到x/primes[j]时，内层for循环就已经可以将x筛掉了。

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

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 =  i + i; j<= n;j+=i) st[j] = true;
    }
}
//线性筛法
void get_primes_1(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] = true;
            if(i % primes[j] == 0) break; // primes[j]一定是i的最小质因子
        }
    }
}

int main(){
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}