P3912 素数个数

skystars

题目描述
求 1,2,⋯,N 中素数的个数。

输入格式
一行一个整数 N。

输出格式
一行一个整数，表示素数的个数。

输入输出样例
输入 #1
10
输出 #1
4

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;

int countPrimes(int n) {
	if (n < 2) return 0;
	int r{ int(sqrt(1.0 * n)) };
	vector<int> V(r, n);
	for (int i = 0; i < r; i++) {
		V[i] /= (i + 1);
	}
	for (int d = V.back() - 1; d > 0; d--) {
		V.push_back(d);
	}
	unordered_map<int, int> S;
	for (auto v : V) {
		S[v] = v - 1;
	}
	for (int p = 2; p <= r; p++) {
		if (S[p] == S[p - 1]) continue;
		int p2{ p * p };
		int sp_1{ S[p - 1] };
		for (auto v : V) {
			if (v < p2) {
				break;
			}
			S[v] -= S[v / p] - sp_1;
		}
	}
	return S[n];
}

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