에라토스테네스의 체 (JAVA)

알고리즘 문제를 풀다보면 소수를 다루는 문제가 종종 보인다.

 

그럴때 사용하기 좋은게 바로 에라토스테네스의 체인데,

 

먼저 위키에 잘나와있으니 한번 읽어 보고 오도록 하자.

 

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부터 시작해 기준인 2를 제외한 2의 배수를 모두 지우고,

남은 숫자중 다음 숫자인 3으로 진행 3을 제외한 3의 배수를 모두 지운다.

 

즉 소수인 i를 제외한 i의 배수를 모두 지우는 과정을 반복해

남는 숫자들이 곧 구하고자하는 구간의 소수가 되는것이다.

 

 

그럼 바로 코드로 구현해보도록 하겠다.

 

구하고자 하는 구간이 1부터 1_000_000 이라 가정해보도록 하겠다.

 

우선 범위 내 숫자들을 의미하는 배열을 하나 선언해주겠다.

 

	static final int end = 1_000_000;
	static boolean[] primeArr = new boolean[end];

 

 

그리고 0,1은 소수가 아니므로 소수가 아님 처리를 true 로 표현 해주도록 하겠다.

 

	static void eratos() {
		primeArr[0] = primeArr[1] = true;

	}

 

즉 해당 메소드를 호출하면 boolean 배열에서 false 인 숫자들이 소수를 의미하는 숫자가 될 것이다.

 

그리고 첫 소수인 2부터 진행해 구간의 마지막까지 확인할 것이므로,

다음과 같은 반복문을 작성할수 있다.

 

	static void eratos() {
		primeArr[0] = primeArr[1] = true;
		for(int i = 2; i*i < end; i++) {
			for(int j = i*i; j < end; j += i) {
				primeArr[j] = true;
			}
		}
	}

 

부연 설명을 하자면, 

 

i < end 가 아닌 i*i < end 인 이유는

 

다음과 같은 간단한 증명이 가능하다.

 

 

$$n = a\times b이고,$$

$$n' = \sqrt{n}일때$$

$$a\geq n' 이면, b \leq n' 이다.$$

 

 

즉, n의 제곱근까지만 검사를 한다면 범위 내의 모든 합성수를 검사해 남은수가 소수임을 알 수 있는 것이다.