AcWing 868. 筛质数

题目

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

输入格式 共一行，包含整数 $n$。

输出格式 共一行，包含一个整数，表示 $1∼n$ 中质数的个数。

数据范围 $1≤n≤10^6$ 输入样例：

8

输出样例：

4

思路

1. 朴素筛选 遍历到某个数值 $i$ 我们将它的倍数全部删除，如此反复，剩下的为 $1∼n$ 中的所有质数

代码

朴素筛选法

#include <iostream>

using namespace std;

const int N = 1000010;

int n, primes[N];
bool st[N];

int find_primes(int x)
{
    int cnt = 0;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
    
        for (int j = i; j <= n; j += i) st[j] = true;
    }
    
    return cnt;
}

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