C++ 알고리즘 - 백준 4948 베르트랑 공준 (에라토스테네스의 체)

https://www.acmicpc.net/problem/4948

 

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

int prime[250000];

void CPP_INIT() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main(void) {
	CPP_INIT();

	for (int i = 2; i < 250000; i++) {
		prime[i] = i;
	}

	for (int i = 2; i <= sqrt(250000); i++) {
		if (prime[i] == 0) continue;

		for (int j = i * i; j <= 250000; j += i) {
			prime[j] = 0;
		}
	}

	int num;

	while (true) {
		int cnt = 0;

		cin >> num;

		if (num == 0) return 0;

		for (int i = num + 1; i <= num * 2; i++) {
			if (prime[i] != 0) cnt++;
		}

		cout << cnt << endl;
	}
}