[알고리즘]에라토스테네스의 체 (소수 찾기)

 

 에라토스테네스의 체는 소수를 찾는 알고리즘이다.

 

고대 그리스 수학자 에라토스테네스가 발견하여 에라토스테네스의 체라고 불려온다.

 

보통 프로그래밍에서 소수를 구하는 여러가지 방법이 있는데 아래와 같이 for문을 중첩사용하여서 현재 숫자가 1 그리고 자기 자신이외에 값으로 나누어 지는지 확인하고 나누어 떨어지지 않으면 소수로 판명한다.

 

// 예제 소수의 갯수를 구하는 코드
int n = int.Parse(Console.ReadLine());
int[] num = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

for(int i = 0; num.Length > i; i++)
{
    if(num[i] == 1)
    {
        n--;
        continue;
    }
    
    for(int k = 2; num[i] > k; k++)
    {
        if(num[i] % k == 0)
        {
            n--;
            break;
        }
    }
}

Console.Write(n);

 

위에 코드에서 문제점은 모든 숫자를 전부 하나씩 검증하기 때문에 값이 많아지면 시간이 그만큼 많이 소요되는 부분을 볼수 있다.

 

그 문제를 해결하기 위해서 에라토스테네스의 체라는 알고리즘을 활용하게 된다.

 

에라토스테네스의 체는 마치 체로 치듯이 수를 걸러낸다고 하여서 에라토스테네스의 체라고 불린다.

 

에라토스테네스의 동작 방식을 설명한 그림은 아래와 같다.

 

에라토스테네스의 동작 방식

그림처럼 1~120까지의 소수를 구하는 에라토스테네스의 체 알고리즘의 동작 방식은 다음과 같다.

1. 먼저 자연수 1을 제거해준다.

2. 2를 제외한 2의 배수를 제거

3. 3을 제외한 3의 배수를 제거

4. 4는 이미 2의 배수에서 제거 되었기 때문에 진행할 필요가 없다.

5. 5를 제외한 5의 배수를 제거

6. 6은 이미 2의 배수에서 제거 (4번과 동일)

7. 7을 제외한 7의 배수를 제거

...

위에 과정을 반복하면 남는 수는 모두 소수이다.

 

아래는 아라토스테네스의 체를 코드를 구현한 내용이다.

// 에라토스테네스의 체 (m 이상 ~ n 이하의 소수를 구하는 방법)
using System.Text;

int[] mn = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int m = mn[0];
int n = mn[1];
// 소수인지 판별을 위한 bool 배열
bool[] num = new bool[n + 1];
// 출력을 담아줄 sb
StringBuilder sb = new StringBuilder();

// 자연수 1을 제거
num[0] = true;

// 2부터 최대값까지의 소수를 구함
for(int i = 2; i <= n; i++)
{
	//제거된 값은 계산하지 않음
    if(!num[i])
    {
    	// 자기 자신을 제외한 배수인 부분을 제거 (2, 3, 5... 순으로 최댓값까지만 계산됨)
        for(int j = 2 * i; j <= n; j += i)
        {
            num[j] = true;
        }
		
        // 최소값 이상의 소수를 String Builder에 저장
        if (i >= m) 
        {
            sb.AppendLine((i).ToString());
        }
    }
}

// String Builder(소수 저장) 출력
Console.Write(sb);

이처럼 에라토스테네스의 체를 이용하면 모든 숫자를 검증하지않고도 프로그래밍상에서 빠른 속도로 소수를 구현하는것이 가능해진다. 

 

물론 해당 방식은 특정한 조건을 가진 문제에서는 시간이 좀더 느리게 출력될수도 있다 무조건적으로 빠른 속도를 가지는 것이 아닌 다수의 소수를 찾아야되는 문제에서 강력한 힘을 발휘해주는 알고리즘이다.

 

여기서 C#이라면 시간을 더 줄이긴 위한 StringBuilder()도 중요하다.

그대로 C#의 출력인 WriteLine메소드로 출력하는 방식도 있지만 해당 방식을 사용할 경우에는 StringBuilder에 비해서 약 수십배의 속도 차이가 나기 때문에 혹여 자신이 해결할 문제에 시간에 제약이 있다면 꼭 StringBuilder()를 사용하여 출력의 시간을 줄여주는것이 좋다.