[C++] 베르트랑 공준 : 4948번

문제

 

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

 

시간제한 : 1초

입력범위 : 1 ≤ n ≤ 123,456

 

---

해석

 

문제를 풀기 위해서는 '에라토스테네스의 체' 를 알아야만 한다.

이걸 몰라도 구현과 결과는 나오겠지만, 백준 사이트에서 시간초과가 날 것이다.

 

에라토스테네스의 체는 생각보다 별거없다.

 

구하고자 하는 범위까지의 소수를 구하는 알고리즘이다.

방법은 다음과 같다.

 

1. 구하고자 하는 범위의 모든 숫자를 나열한다.

2. 2의 두번째 배수(4) 부터 시작하여 2의 배수를 모두 제거한다.

3. 3의 두번째 배수(6) 부터 시작하여 3의 배수를 모두 제거한다.

4. 이 과정을 반복하여 어떤 소수의 모든 배수를 제거한다.

5. 범위 내에는 소수만 남게 된다.

 

어떤 수의 배수는 소수가 아니라는 원리를 이용한 것이다.

---

풀이

#include <iostream>
#include <cmath>
using namespace std;

#define MAX 123456 * 2

int main()
{
	int N; // 주어진 수
	bool isPrime[MAX + 1] = { true, }; // 소수인지?
	int count = 0; // 갯수 저장

	for (int i = 2; i <= MAX; i++) // isPrime 초기화
	{
		isPrime[i] = true;
	}

	isPrime[0] = false;
	isPrime[1] = false;
	// 에라토스테네스의 체
	for (int i = 2; i <= sqrt(MAX); i++)
	{
		for (int j = i * 2; j <= MAX; j += i)
		{
			isPrime[j] = false; // 2..3...어떤 수의 배수는 소수가 아님
		}		
	}

	while (true)
	{
		cin >> N; // 입력
		if (N == 0) break; // 0 입력 시 종료

		count = 0;

		for (int i = N + 1; i <= 2 * N; i++) // isPrime 이 true인 경우만 세서 출력
		{
			if (isPrime[i] == true)
			{
				count++;
			}
		}
		cout << count << "\n";
	}
}