#include <iostream> #include <vector> using namespace std; int main() { // 1. 输入整数 n int n; cin >> n; if (n < 2) { // 小于2没有素数，直接输出0 cout << 0 << endl; return 0; } // 2. 埃氏筛法：标记是否为素数 vector<bool> is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; // 0和1不是素数 for (int i = 2; i * i <= n; ++i) { if (is_prime[i]) { // 把i的倍数全部标记为非素数 for (int j = i * i; j <= n; j += i) { is_prime[j] = false; } } } // 3. 统计素数数量 int count = 0; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { count++; } } // 4. 输出结果 cout << count << endl; return 0; }