[C언어] Backjoon_Code 4948, 베르트랑 공준

| 문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

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

 

| 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

 

| 출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

 

| 제한

• 1 ≤ n ≤ 123,456

 

| 예제 입력 1

1
10
13
100
1000
10000
100000
0

| 예제 출력 1

1
4
3
21
135
1033
8392

 

| 문제의 키 포인트

1. 비교적 규칙은 간단하다. 이전 소수 구하기 문제에서는 범위 M과 N을 입력받아서 해당하는 소수값을 출력했지만, 이 문제에서는 n만을 입력받아 범위를 지정한다.

 

| 해결방안(Solution)

1. 이전 소수 구하기 문제에서 활용한 에라토스테네스의 체를 활용한다.

2. 풀이 형태는 두 가지될 수 있다.

(풀이 1): 입력받은 범위 사이즈만큼의 소수배열을 만들고 소수의 개수를 출력하기

(풀이 2): 소수배열을 제한된 범위의 사이즈 만큼 만들어서 이후 입력받은 값에 대해 소수의 개수를 출력하기

두 풀이마다 장단점이 있기 때문에, 상황에 맞춰 사용하는 것이 좋다고 판단이 된다.

 

| 소스코드 1(SourceCode 1)

풀이 1의 형태로 작성한 코드입니다.

// BOJ_4948_Betrand_Postulate, 베르트랑 공준
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define size 123456 * 2 + 1

int main(void)
{
	int n, i, j, k;
	int arr[size] = { 0, };
	int cnt = 0;

	while (1)
	{
		scanf("%d", &n);

		if (n == 0)
		{
			break;
		}

		k = 2 * n;
		arr[0] = 1, arr[1] = 1;
		for (i = 2; i <= k; i++) // 입력값만큼 소수 배열 생성
		{
			if (arr[i] == 1)
			{
				continue;
			}
			else
			{
				for (j = 2; i * j <= k; j++)
				{
					arr[i * j] = 1;
				}
			}
		}

		for (i = n+1; i <= k; i++) // 소수의 개수 계산
		{
			if (arr[i] == 0)
			{
				cnt++;
			}
		}
		printf("%d\n", cnt);
		cnt = 0;
	}
	
	return 0;
}

 

| 소스코드 2(SourceCode 2)

풀이 2의 형태로 작성한 코드입니다.

// BOJ_4948_Betrand_Postulate, 베르트랑 공준_2
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define size 123456 * 2 + 1

int main(void)
{
	int n, i, j, k;
	int arr[size] = { 0, };
	int cnt = 0;

	arr[0] = 1, arr[1] = 1;
	for (i = 2; i <= size; i++) // 사이즈만큼 소수 배열 생성
	{
		if (arr[i] == 1)
		{
			continue;
		}
		else
		{
			for (j = 2; i * j <= size; j++)
			{
				arr[i * j] = 1;
			}
		}
	}

	while (1)
	{
		scanf("%d", &n);

		k = 2 * n;
		
		if (n == 0)
		{
			break;
		}

		for (i = n + 1; i <= k; i++) // 소수의 개수 계산
		{
			if (arr[i] == 0)
			{
				cnt++;
			}
		}
		printf("%d\n", cnt);
		cnt = 0;
	}

	return 0;
}

 

| 결과 비교

▲ 풀이 1의 경우

▲ 풀이 2의 경우

풀이 1보다 풀이 2가 60ms 더 빠른 결과를 보여줬네요.

깔끔하게 작성하고자 문단을 나눠서 코드는 길어졌지만, 거의 일치한다고 보았을 때 전체 사이즈만큼 소수 배열을 만들어 놓고, 거기에서 소수의 개수를 출력해내는 풀이 2 방식이 속도면에서는 더 좋네요.

 

그럼 오늘도 즐거운 코딩!

 

| 문제출처

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

4948번: 베르트랑 공준