백준 4948번 베르트랑 공준

에라토스테네스의 채를 이해하면 금방 풀 수 있다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
bool cache[123456 * 2 + 1];
int main() {
	vector<int> inputs;
	int a;
	while (true) { //input
		cin >> a;
		if (a == 0 || a > 123456) break;
		inputs.push_back(a);
	}

	for (int i = 2; i < 123456 * 2; i++)
		cache[i] = true;
	for (int i = 2; i < sqrt(123456 * 2); i++) {
		if (cache[i]) {
			for (int j = i + i; j <= 123456 * 2; j += i) {
				cache[j] = false;
			}
		}
	}

	for (int i = 0; i < inputs.size(); i++) {
		int count = 0;
		for (int j = inputs[i]+1; j <= inputs[i]*2; j++) {
			if (cache[j]) {
				count++;
			}
		}
		cout << count << endl;
	}
}