[백준알고리즘] 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;
	}
}

 

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