#include <iostream>
#include <vector>
using namespace std;

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

    vector<bool> is_prime(n + 1, true);
    is_prime[1] = false;

    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    int cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) cnt++;
    }
    cout << cnt << endl;
}

过10道【分支结构】的官方题目

分支·分支解题者

过10道【输入输出】的官方题目

I/O·IO入门者

过10道【贪心】知识点对应题目

贪心·贪心尝试者

过10道【循环结构】的官方题目

循环·循环打卡人

倔强青铜

要用到欧拉筛法哦！这样才能O（1）
```cpp
def sieve(n):
    isprime=[True]*(n+1)
    prime=[]
    for i in range(2,n+1):
        if isprime[i]:
            prime.append(i)
        for p in prime:
            if p*i>n:
                break
            isprime[p*i]=False
            if i%p==0:
                break
    return prime
print(len(sieve(int(input()))))
```


不用再算了

题解

出道萌新

过10道【格式化输入输出】的官方题目

格式·格式排版员

过10道【一维数组】的官方题目

数组·数组操作员

要用到欧拉筛法哦！这样才能O（1）

全部评论 1