传送门

直接用函数($\Theta(n\sqrt{n})$)

#include <bits/stdc++.h>

using namespace std;

bool prime(int n) { // 素数判断函数 sqrt(n)
    if (n <= 1) {
        return 0;
    } else if (n == 2) {
        return 1;
    } else {
    	for (int i = 2; i * i <= n; i++) {
    		if (n % i == 0) {
    			return 0;
			}
		}
	}
    return true;
}
int n;

int main() {
    cin >> n;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {  // 线性暴力，直接乘 n
    	if (prime(i)) {
    		cnt++;
		}
	}
	cout << cnt;
    return 0;
}

可惜这个代码只能 60 分，因为 $n$ 的大小有 $1e8$

埃氏筛（$\mathcal{O} (\sqrt{n}\log\log n)$）

#include <bits/stdc++.h>

using namespace std;

const int N = 1e8 + 10;
int cnt;
bool flag[N];
void init(int n) {
	flag[1] = 1;
	for (int i = 2; i * i <= n; i++){
		if (flag[i] == 0) {
			for (int j = i * i; j <= n; j += i) { // 以他的倍数都划掉
				flag[j] = 1;
			}
		}
	}
}

int main() {
	int n;
	cin >> n;
	init(n);
	for (int i = 1; i <= n; i++) { // 线性普查
		if (flag[i] == 0) {
			cnt++;
		}
	}
	cout << cnt;
    return 0;
}

欧拉筛（$O(n)$）

出现了不明问题，发布代码时间较长，请耐心等待，谢谢