[백준/C & C++] 4948 베르트랑 공준

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

4948번: 베르트랑 공준

코드 (C)

#include <stdio.h>

int arr[246920] = { 0, };
int main()
{
	int n;
	arr[1] = 1;

	for (int i = 2; i <= 246919; i++)
	{
		if (arr[i] == 1) continue;
		else for (int j = i * 2; j <= 246919; j += i) arr[j] = 1;
	}

	while (1)
	{
		scanf("%d", &n);
		if (n == 0) break;
		else
		{
			int count = 0;
			for (int i = n+1; i <= 2 * n; i++)
			{
				if (arr[i] == 0) count++;
			}
			printf("%d\n", count);
		}
	}
	return 0;
}

코드 (C++)

#include <iostream>
using namespace std;

int arr[246920] = { 0, };

int main()
{
	int n;
	arr[1] = 1;

	for (int i = 2; i <= 246919; i++)
	{
		if (arr[i] == 1) continue;
		else for (int j = i * 2; j < 246919; j += i) arr[j] = 1;
	}

	while (1)
	{
		cin >> n;
		if (n == 0) break;
		else
		{
			int count = 0;
			for (int i = n + 1; i <= 2 * n; i++)
			{
				if (arr[i] == 0) count++;
			}
			cout << count << "\n";
		}
	}
	return 0;
}

코드설명

먼저 에라토스테네스의 체를 이용해서 범위 내의 모든 수를 소수 판별한다.

에라토스테네스의 체를 구현하는 코드의 설명 :  https://0yeonjae2.tistory.com/m/entry/%EB%B0%B1%EC%A4%80C-1929-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0

[백준/C] 1929 소수 구하기

 

while문에서 n으로 0이 입력될 때까지 반복문을 돈다. 

n이 0이 아니면, count라는 변수를 선언하고 0으로 초기화한다. 

문제에 설명된 범위인 n+1부터 n*2까지 반복문을 돌면서 arr[i]에 저장된 값이 0이라면(== 소수) count에 1을 더한다. 

반복문을 다 돈 후 count를 출력한다. 

 

느낀 점

n의 제한이 123456까지라서 처음에 배열을 arr[123457]로 선언하고 코드를 작성했는데, 다음과 같이 결과가 나왔다. 

1000000의 답이 이상하다

그래서 뭐가 문제인지 문제를 다시 읽어보면서 123456가 아니라 123456*2인 246912까지 소수판별이 되어야 한다는 것을 알았다. 범위보다 여유있게 소수판별을 한 후 다시 문제를 푸니 결과도 바르게 나왔다. 이것 빼고는 어려움이 없었다.

문제를 제대로 읽어야 한다는 것을 다시 느낀 문제였다.