#include #include using namespace std;

int countPrimes(int n) { if (n < 2) return 0;

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*i 开始标记，因为比 i*i 小的 i 的倍数已经被比 i 小的素数标记过了
        for (int j = i * i; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
}

int count = 0;
for (int i = 2; i <= n; i++) {
    if (is_prime[i]) {
        count++;
    }
}
return count;

}

int main() { int n; cin >> n;

cout << countPrimes(n) << endl;

return 0;

}