[백준/BOJ] 4948번 베르트랑 공준 (C/C++)

백준 온라인 저지(BOJ) 4948번 베르트랑 공준

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

4948번: 베르트랑 공준

* 사용언어 : C언어, C++

 

1. 문제

입력 n에 대해 n보다 크고 2n보다 작거나 같은 소수의 개수 출력 (0이면 종료)

 

2. 풀이

에라토스테네스의 체를 활용하여 2n 이하 소수를 모두 찾은 후에

n 초과 2n 이하 소수의 개수를 count하여 출력하였습니다.

 

에라토스테네스의 체를 사용할 때 for문의 max값은

2 * 123,456이 아닌 루트를 씌운 값까지 진행하면 됩니다. 

[에라토스테네스의 체 사용 시 루트 n까지만 진행해도 되는 이유]
만약 어떤 수 n이 1과 n이 아닌 다른 수로 나누어 떨어진다면 n은 a * b로 표현할 수 있습니다.
이 때 a가 루트 n보다 크거나 같다면, b는 루트 n보다 작거나 같게 됩니다.

따라서 루트 n보다 작은 b만으로 에라토스테네스의 체를 사용하더라도
n 이하의 모든 소수가 아닌 수를 잡아낼 수 있게 됩니다.

 

이후 설명은 아래 코드로 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
4948_베르트랑 공준
2076KB	4ms
*/
#include <cstdio>
#include <math.h>

const int LM = 123456 * 2 + 1;
const int RLM = sqrt(LM) + 1;
int isNotPrime[LM], n, idx, cnt;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	isNotPrime[1] = 1;
	for (int i = 2; i < RLM; ++i) {
		if (isNotPrime[i]) continue;

		idx = i * 2;
		while (idx < LM) {
			isNotPrime[idx] = 1;
			idx += i;
		}
	}

	while (1) {
		scanf("%d", &n);
		if (n == 0) break;

		cnt = 0;
		for (int i = n + 1; i <= 2 * n; ++i) {
			cnt += !isNotPrime[i];
		}
		printf("%d\n", cnt);
	}
	return 0;
}