[백준알고리즘] 4948번: 베르트랑 공준 -C++

[백준알고리즘] 4948번: 베르트랑 공준 -C++

4948번: 베르트랑 공준 (acmicpc.net)

4948번: 베르트랑 공준

소수 문제들은 다 비슷비슷한 것 같기도 하다.

 

에라토스테네스의 체를 사용해서 가능한 범위의 모든 수들의 소수 여부를 판단해주었다. 이후 입력되는 수에 대해서 에라토스테네스의 체를 이용해 소수 판정을 한다.

 

주의할 점은 입력으로 들어오는 $n$이 $1$ 이상 $123456$ 이하라는 것이고, 문제에서는 $n$보다 크고 $2n$보다 작거나 같은 범위에 대해서 소수의 개수를 구해야 하는 것이다. 따라서 입력 범위의 두 배만큼의 크기로 배열을 만들어주었다.

 

while의 조건문 안에 std::cin을 사용했는데, 이렇게 해도 되나 찾아보았다. cin은 원래 istream 객체를 return한다고 한다. 하지만 stream은 스스로 상태를 true와 false로 파악하는 변환 연산자가 존재한다고 한다. 이 변환 연산자는 if나 while 안에서는 변환된다고 한다.

 

if나 while의 조건문 안에서 cin이 false로 return되는 경우에는 아래와 같이 형이 잘못된 경우라고 한다. 좋은 글이 있어 링크를 첨부한다.

stackoverflow.com/a/6791545

int x;
if (cin >> x) {} 	// 숫자가 아닌 값을 입력할 경우
else {}				// 여기가 실행

 

아래는 본 문제에 대한 코드이다.

#include <iostream>

#define NUM_SIZE 123456
#define TOTAL_SIZE NUM_SIZE * 2 + 1

bool field[TOTAL_SIZE];

void eratosthenes(void);
void solve(void);

int main(void)
{
	eratosthenes();
	solve();
	return 0;
}

void eratosthenes(void)
{
	std::fill_n(field, TOTAL_SIZE, true);

	field[0] = field[1] = false;
	for (int i = 2; i < NUM_SIZE + 1; i++)
	{
		if (!field[i]) continue;

		int temp = 2;
		while (i * temp < TOTAL_SIZE)
		{
			field[i * temp] = false;
			temp++;
		}
	}
}

void solve(void)
{
	int n;
	while (std::cin >> n)
	{
		if (n == 0) break;

		int cnt = 0;
		for (int i = n + 1; i <= 2 * n; i++)
			if (field[i]) cnt++;

		std::cout << cnt << std::endl;
	}
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다