에라스토테네스의 체 (소수 구하기)

소수 구하기 알고리즘은 간단하지만 확실하게 정리해두지 않으면 헷갈리기 좋은 문제라고 생각한다. 하지만 다른 알고리즘들과 마찬가지로 한번만 확실하게 이해해두면 바로바로 구할 수 있기 때문에 한번정도는 정리해두는 것이 좋다.

소수는 정규 교육과정을 거친 사람은 누구나 이해하고 있을만큼 간단한 개념이다. 1을 제외하고 자기 자신으로만 나누어 떨어지는 수. 이것이 소수의 정의이다. 소수에는 많은 수학적 이론과 증명이 배경에 있겠지만 과감히 생략하고 이 정의에 입각하여 알고리즘적으로 소수를 판가름 하는 코드를 작성해보겠다. 소수에 대해서는 아래의 링크를 참고하자.

소수(수론) - 나무위키

https://namu.wiki/w/%EC%86%8C%EC%88%98(%EC%88%98%EB%A1%A0)

소수는 1과 자기 자신을 제외하고는 약수가 있어서는 안된다. 그렇기 때문에 자기 자신보다 작은 수중에서 나누었을 때 0으로 나누어떨어지는 수가 있어서는 안된다는 것이다. 그렇다면 간단하게는 이렇게 표현할 수 있겠다.

	public boolean isPrimeNumber(int num) {
		for (int i = 2; i < num; i++) {
			if(num % i == 0)
				return false;
		}
		return true;
	}

하지만 굳이 이렇게 2부터 자기 자신보다 하나 작은 숫자까지 나눠줄 필요가 있을까 생각해보면 그렇지 않다는 것을 쉽게 깨달을 수 있다. 예를 들어 8이 소수인지 확인해보자. 8은 약수로 1, 2, 4, 8을 갖고 있다. 8이 소수인지 알기위해서는 1과 8을 제외한 약수가 있는지 찾아봐야하는데 2를 약수로 찾게되면 8을 2로 나눈 몫인 4는 탐색하지 않아도 이미 8이 소수가 아닌 것을 확인할 수 있게된다. 그렇다면 어디까지 확인을 해보는 것이 최소한으로 약수가 있는지 없는지 판단할 수 있는 경계가 될까. 경계는 판단하려고 하는 숫자의 양의 제곱근이다. 가령 9가 소수인지 확인해보려면 9의 양의 제곱근인 3까지 판단하면 되고 16이라면 4까지 판단하면 되는 것이다. 판단범위가 확 줄게 되면서 시간복잡도 면에서 확실히 많은 이득이 있었다.

	public boolean isPrimeNumber(int num) {
		for (int i = 2; i <= Math.sqrt(num); i++) {
			if(num % i == 0)
				return false;
		}
		return true;
	}

Math.sqrt() 메서드를 이용해서 제곱근을 구하자.

이제 특정 범위의 숫자들이 소수인지 아닌지 판단하는 문제가 있다고 해보자. 위의 방식으로 소수인지 아닌지 구한다면 상당히 많은 연산이 필요로 하게 된다. 범위를 정하고, 그 범위에서 숫자 하나를 뽑아서 위의 메서드에 집어넣어 판단하고 소수가 아니면 넘어가고 소수이면 체크하고, 이 방식으로는 불필요한 연산이 너무 많이 들어가게 된다. 그렇기 때문에 특정 숫자들의 범위 내에서 소수만을 뽑아내기 위해 에라스토테네스의 체라는 알고리즘을 사용한다.

에라토스테네스의 체 - 위키백과

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라스토테네스는 사람이름이고 체는 걸러내는 도구이니까 적어도 어떠한 필터를 이용하여 체로 걸러 소수만 남길 것임을 알 수 있다. 방식은 아주 간단하다. 일단 2부터 특정 숫자까지 원하는 범위를 정한다. 그리고 그 안에서 순차적으로 소수를 구하고 그 소수의 배수들을 모두 제거하는 방식으로 범위를 좁혀가면서 소수를 구하는 것이다. 

1	2	3	4	5	6	7	8	9	10
2	3	4	5	6	7	8	9	10	11

위와 같은 배열이 있을 때 소수인 2부터 시작해서 2로 나누어떨어지는 수들을 체로 걸러내듯 걸러준다. 이때 체의 기준이 되는 2는 소수라는 의미에서 따로 표시를 해준다.

1	2	3	4	5	6	7	8	9	10
2	3	4	5	6	7	8	9	10	11

2는 소수이지만 2로 나누어떨어지는 수들은 소수가 아니기 때문에 배열에서 제외시키고 2만 소수배열에 포함시킨다. 이렇게 한번 체로 걸러지고 남은 숫자들에서 다시 소수인 3을 기준으로 다시 걸러준다.

1	2	3	4	5	6	7	8	9	10
2	3	4	5	6	7	8	9	10	11

그 다음은 5, 7, 11의 순서로 걸러주게 되면 체에 걸리는 4, 6, 8, 9, 10은 소수가 아닌 숫자로 구분되게되고, 나머지 2, 3, 5, 7, 11은 소수라는 사실을 알 수 있다.

백준 온라인 저지의 베르트랑 공준 문제를 풀면서 이해해보도록 하자.

4948번: 베르트랑 공준 - Baekjoon Online Judge

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

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static final int S = 246913;

	public static void main(String[] args) {
		boolean[] check = new boolean[S];
		boolean[] prime = new boolean[S];
		check[0] = true;
		check[1] = true;

		int idx = 2;
		while (idx < S) {
			if (check[idx]) {
				idx++;
			} else {
				check[idx] = true;
				prime[idx] = true;
				for (int i = idx; i < S; i += idx) {
					check[i] = true;
				}
			}
		}

		int tmp = 0;
		int cnt = 0;
		while ((tmp = nextInt()) != 0) {
			cnt = 0;
			for (int i = tmp + 1; i <= 2 * tmp; i++) {
				if (prime[i])
					cnt++;
			}
			System.out.println(cnt);
		}
	}

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static int nextInt() {
		int tmp = 0;
		try {
			tmp = Integer.parseInt(br.readLine().trim());
		} catch (Exception e) {
			e.printStackTrace();
		}
		return tmp;
	}
}