[에라토스테네스의 체] 소수를 구하는 알고리즘

소수란,

" 1과 자신만을 약수로 가지는 수" 를 의미한다.

 

죠죠의 엔리코 푸치 신부는 마음의 평정을 유지하기 위해 소수를 셌다.

우리에게 평안을 가져다주는 소수, 어떻게 구할 것인가?

 

이번 글의 주제인 "에라토스테네스의 체" 라는 고대 그리스 수학자의 알고리즘에 대해 알아보기 전에,

간단한 알고리즘부터 살펴보자.

---

# 1 범위 내의 모든 정수들 가지고 그보다 작은 수들로 나눠본다.

누구나 상상할 수 있고, 가장 간단한 방법.

범위 내의 모든 수를 가지고 소수인지를 판별하는 방법이다.

 

소스코드로 나타내면 이러하다.

template <typename T>
bool Check(T input)
{
	for (int i = 2; i <= input; i++)
	{
		if (input % i == 0)
			return false;
	}
	return true;
}

 

구현도 간단하지만 모든 데이터를 순회하므로 O(n)의 시간 복잡도가 발생한다.

 

데이터가 너무 많아지면... 너무 느리다. 더 빠른 방법은 없을까?

 

#2 제곱근까지만 확인하기.

정수론에 의하면, 

 

"자신의 제곱근보다 작은 수로 나누어지지 않을 경우, 그 정수는 소수이다."

라고 한다.

 

이를 통해 우리는 2부터 n의 제곱근까지으로만 나눠서 소수를 판별할 수 있다.

template <typename T>
bool Check(T input)
{
	T sqrt_input = std::sqrt(input);
	for (int i = 2; i <= sqrt_input; i++)
	{
		if (input % i == 0)
			return false;
	}
	return true;
}

 

#1 의 코드와 유사하지만, 제곱근까지만 값을 나누어보고 bool 값을 리턴하고 있다.

 

for문의 범위가 n -> √n이 되면서 시간 복잡도는 O(√n)가 되었다.

#1의 알고리즘보다 꽤나 많이 빨라졌다.

 

다만, 이보다도 더 괜찮은 방법이 아직 존재한다.

이제 에라토스테네스의 체에 대해서 알아보자.

#3 에라토스테네스의 체

 

고대 그리스의 수학자 에라토스테네스가 만든 소수를 찾기 위한 방법이다.

 

숫자들을 딱 깔아놓고, 소수를 제외한 수들을 하나하나 체로 치듯이 수를 걸러내는 방법.

 

2의 배수, 3의 배수, 5의 배수.... n의 배수를 배열에서 제거해나가면,

결국 배열에는 소수만이 남는다.

 

언뜻 노가다같지만, 노가다가 맞다.

void eras(int a, int b)
{
	for (int i = a; i <= b; i++)
	{
		inputs[i] = i;
	}
	for (int i = 2; i <= std::sqrt(b); i++)
	{
		for (int j = i * i; j <= b; j += i)
		{
			if (inputs[j] != 0) inputs[j] = 0;
		}
	}
	for (int i = a; i <= b; i++)
	{
		if (inputs[i] != 0 && inputs[i] != 1) std::cout << inputs[i] << '\n';
	}

}

 

위의 두 알고리즘과 다른 테스트케이스로 테스트해서 코드 구조가 조금 상이한데,

핵심은 두 번째 for문이다.

 

2의 배수부터 차근차근 배열에서 그 값을 제거한다.

이 때, 구하고 싶은 범위 최댓값의 제곱근의 배수까지만 제거해주면 된다.

 

1 ~ 100 사이의 모든 약수를 구하고싶다면,

2의 배수부터 10의 배수까지만 계산해주면 된다는 이야기.

물론 2의 배수를 제거하면서 10의 배수도 자연스럽게 사라졌겠지만.

 

에라토스테네스의 체는 시간복잡도가 O(nloglogn)으로,

앞의 두 알고리즘보다 빠른 속도를 자랑한다.

---

 

마지막으로, 에라토스테네스의 체를 이용해 백준 4949번 문제 "베르트랑 공준"을 풀어보았다.

입력으로 받은 n과 2n사이에 몇 개의 소수가 있는지를 출력하는 문제다.

#include <iostream>
#include <vector>
#include <math.h>

int nums[1000000];

int Check2(int n, int nn)
{
	int count = 0;
	for (int i = n; i <= nn; i++)
	{
		nums[i] = i;
	}
	for (int i = 2; i <= std::sqrt(nn); i++)
	{
		for (int j = i * i; j <= nn; j += i)
		{
			if (nums[j] != 0)
			{
				nums[j] = 0;
			}
		}
		
	}
	for (int i = n + 1; i <= nn; i++)
	{
		if (nums[i] != 0)
			count++;
	}

	return count;
}

int main()
{
	int n;
	std::cin >> n;
	while (n != 0)
	{
		std::cout << Check2(n, n * 2) << '\n';
		std::cin >> n;
	}
	return 0;

}

 

위와 같이, 일정 범위 내의 소수를 찾을 때는

에레토스테네스의 체 알고리즘을 사용할 수 있다.

 

---

 

구현하기가 간단하고 빠른 알고리즘인데,

#1과 #2 알고리즘과는 다르게 그 존재를 모르면 구현이 거의 불가능하다.

 

프로그래머에게 수학적 이론이 중요하다는 것을 직접 체감할 수 있고,

성능도 (일정 범위 내의 모든 소수를 찾는 데에 있어서는) 최고 수준의 성능을 발휘하므로,

이래저래 멋진 알고리즘이 아닌가.