베르트랑 공준 (feat. 백준, 4948번)

베르트랑 공준
https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/4948
#include <iostream>
#include <cmath>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	register bool arr[123456 * 2 + 1] = { false };
	arr[0] = arr[1] = true;
	register int e = sqrt(123456 * 2);
	for (register int i = 2, j; i <= e; ++i)
		if (!arr[i])
			for (j = i << 1; j <= 123456 * 2; j += i)
				arr[j] = true;
	while (true) {
		cin >> N;
		if (!N)		break;
		register int ans = 0;
		for (register int i = N + 1; i <= 2 * N; ++i)
			if (!arr[i])			++ans;
		cout << ans << "\n";
	}
	return 0;
}
// *&)*@*

문제로 주어진 N의 2배만큼 미리 소수를 구해두고, 문제에서 주어진 N+1 ~ 2N까지 소수의 개수를 구하는 방법입니다.

이 또한 "에라토스테네스의 체" 로 미리 소수를 구했습니다. 아래 문제를 선행하시길 권장합니다.

소수 찾기 (feat. 백준, 1978번)