[C/C++] 백준 4948: 베르트랑 공준(소수)

베르트랑 공준

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

4948번: 베르트랑 공준

베르트랑 공준은 임의의 자연수 $n$에 대해서 $n$보다 크고 $2n$보다 작거나 같은 소수는 적어도 하나 존재한다는 내용이다. 예를 들어 $n=10$일 때, $10$보다 크고 $20$보다 작거나 같은 소수는 $11, 13, 17, 19$로 총 4개 존재한다. 백준의 4948번: 베르트랑 공준 문제는 임의의 자연수 $n$을 입력받았을 때, $n$ 보다 크고 $2n$보다 작거나 같은 소수의 개수를 찾는 문제이다.

이 문제에서의 핵심 사항은 다음과 같다.

• 여러 개의 $n$을 입력 받아 반복적으로 소수의 개수를 출력해야 한다.
• $n$의 값이 큰 경우에도 효율적으로 소수를 찾아낼 수 있어야 한다.

그렇다면 소수를 효율적으로 구할 수 있는 방법은 무엇일까?

소수 확인 방법

가장 기본적으로 소수를 확인하는 함수의 기본형은 다음과 같다.

bool IsPrime(int n)
{
    if (n==1)
    {
    	return false;
    }
    for (int i = 2; i < n; i++)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}

입력받은 $n$이 $1$인 경우, $1$은 소수의 정의에 의해 소수가 아니므로 $false$를 출력한다. $1$이 아닌 경우에는 $2$부터 크고 자기 자신보다 하나 작은 자연수 $n-1$까지의 모든 값에 대해서 나누어 떨어지는지 확인하고, 나누어 떨어지는 경우에는 $false$이고, 아닌 경우에는 $true$이다.

이 방법의 큰 단점은 바로 n이 커질 수록 반복 회수가 커진다는 의미이다. 백준 4948번: 베르트랑 공준 문제는 자연수 $n$부터 $2n$까지의 모든 자연수를 검사해야 하므로 수행 시간은 대략 $O(N^2)$만큼 커진다는 의미이다. 이를 해결하기 위해서 첫 번째 방법은 에라토스테네스의 체를 사용하는 것이 있는데, 이것의 아이디어는 확인된 소수의 정수배인 자연수는 모두 소수가 될 수 없다는 것부터 시작이다. 이 문제에 에라토스테네스의 체를 사용 하기에는 검사해야 할 자연수의 개수가 너무 많다는 점이다. 이로 인해 문제에서 정의한 $n$이 가질 수 있는 모든 범위의 자연수에 대한 배열을 만들기 위한 메모리의 낭비와 소수의 모든 정수배인 자연수가 소수가 아님을 체크하는 과정에서 수행 시간 낭비가 발생할 수 있다.

두 번째 방법은 검사 횟수 자체를 줄이는 것이다. 이는 자연수가 가질 수 있는 공약수들을 토대로 만든 아이디어이다. 자연수 $n$이 서로 다른 두 개의 자연수 $a, b$로 이루어져 있고, 각각은 다음과 같은 관계를 가진다.

$n = ab$

$0 < a {\leq} b < n$

이 경우 $a^2$은 $n$보다 작거나 같고, $b^2$은 $n$보다 큰거나 같은 값을 같는다. 즉, 다음과 같은 관계식을 만족한다.

$a^2 {\leq} n {\leq} b^2$

$a {\leq} {\sqrt{n}} {\leq} b$

이다. 따라서 자연수 $n$이 소수인지 판별하기 위해서 $n-1$까지의 값을 검사할 필요 없이 $2$부터 $[{\sqrt{n}}]$보다 작은 모든 값을 검사하면 된다. 여기서 $[x]$는 $x$보다 작거나 같은 정수를 의미한다. 설명은 복잡했지만 결과만 활용해 소수 검사 함수를 만들면 다음과 같다.

bool IsPrime(int n)
{
	if (n == 1)
		return false;

	for (int i = 2; (i*i) <= n; i++)
	{
		if (n % i == 0)
		{
			return false;
		}
	}
	return true;
}

여기서 $sqrt(n)$이 아닌 $i*i$를 쓴 이유는 제곱근을 계산 하는 것보다 두 수를 곱하는 것이 수행 시간적으로 더 빠르기 때문이다.

따라서 4948번: 베르트랑 공준의 제출 코드는 다음과 같다.

#include <iostream>
#include <cstring>

using namespace std;

bool IsPrime(int n)
{
	if (n == 1)
		return false;

	for (int i = 2; (i*i) <= n; i++)
	{
		if (n % i == 0)
		{
			return false;
		}
	}
	return true;
}

int main(void)
{
	int n = 1, count = 0;

	while (n != 0)
	{
		cin >> n;
		if (n == 0)
			break;
		count = 0;

		for (int i = (n + 1); i <= (2 * n); i++)
		{
			if (IsPrime(i))
			{
				count++;
			}
		}

		cout << count << "\n";
	}

	return 0;
}