백준 4948 - 베르트랑 공준

문제 번호: 4948

문제 제목: 베르트랑 공준

문제 주소: https://www.acmicpc.net/problem/4948

문제 내용

n보다 크고 n * 2보다 작거나 같은 소수의 개수를 출력한다.
0이 입력되는 경우 종료한다.

테스트 케이스

1 10 13 100 1000 10000 100000 0

1 4 3 21 135 1033 8392

문제 풀이

각 수마다 소수인지 확인하는 방식으로 풀어도 통과는 가능하다.
다만 0이 입력될 때까지 소수인지 확인하는 작업이 반복되기 때문에 에라토스테네스의 체를 이용하는 편의 시간이 짧다.

풀이 코드

#include <iostream>
using namespace std;
// 각 수마다 소수인지 확인하는 방식
void BAEKJOON_4948()
{
	int n;
	while (cin >> n && n != 0)
	{
		int countPrime = 0;
		for (int i = n + 1; i <= n * 2; i++)
		{
			bool isPrime = true;
			if (i > 2 && i % 2 == 0)
			{
				isPrime = false;
			}
			else
			{
				for (int j = 3; j * j <= i; j += 2)
				{
					if (i % j == 0)
					{
						isPrime = false;
						break;
					}
				}
			}
			if (isPrime)
			{
				countPrime++;
			}
		}
		cout << countPrime << endl;
	}
	return;
}

// 에라토스테네스의 체를 이용한 방식
void BAEKJOON_4948()
{
	int n;
	bool primeArr[246913] = { false };
	for (int j = 4; j <= 246912; j += 2)
	{
		primeArr[j] = true;
	}
	for (int i = 3; i <= 246912; i += 2)
	{
		for (int j = i * 3; j <= 246912; j += i * 2)
		{
			primeArr[j] = true;
		}
	}

	while (cin >> n && n != 0)
	{
		int countPrime = 0;
		for (int i = n + 1; i <= n * 2; i++)
		{
			if (!primeArr[i])
			{
				countPrime++;
			}
		}
		cout << countPrime << endl;
	}
	return;
}