[C++] 백준 4948. 베르트랑 공준

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

n보다 크고 2n보다 작거나 같은 소수의 개수를 출력하는 문제이다.

풀이

베르트하고 공준이라는 사람이 있는줄 알았다.
수학 교양 +1

이번에도 에라토스테네스의 체를 써서 풀었는데
자꾸 틀렸다고 나오는겨

오잉 13부터 26까지 소수는 13, 17, 19, 23 네 갠데? 했는데
알고보니 'n보다 크고 2n보다 작거나 같은' 소수를 구해야 했던 것
문제를 제대로 읽자 ~

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<bool> isPrime(250000, true);

void getPrime() {
	isPrime[0] = false;
	isPrime[1] = false;

	for (int i = 2; i < 250000; i++) {
		if (isPrime[i]) {
			for (int j = i * 2; j < 250000; j += i) {
				isPrime[j] = false;
			}
		}
	}

	return;
}

void cntPrime() {
	int cnt = 0;
	for (int i = n + 1; i <= 2 * n; i++) {
		if (isPrime[i]) cnt++;
	}
	cout << cnt << "\n";

	return;
}

int main() {
	getPrime();

	while (1) {
		cin >> n;
		if (n == 0) break;
		cntPrime();
	}

	return 0;
}

채점