[알고리즘] 에라토스테네스의 체 - JAVA(자바)

에라토스테네스의 체(Sieve of Eratosthenes)

• 고대 그리스의 수학자 에라토스테네스가 만들어 낸 방법으로 체처럼 걸러낸다고 해서 붙여진 이름이다. 많은 수 중 소수를 판별해야 할 때, 사용하는 대표적인 알고리즘이다.
  • 먼저 소수를 판별해야 하는 범위만큼의 크기를 가진 배열을 생성한다.
  • 소수가 아닌 1은 제외한다.
  • 가장 작은 소수인 2부터 시작해서 2를 제외한 2의 배수들을 제외한다. 다음  큰 소수인 3도 3을 제외하고 3의 배수들도 마찬가지로 제외한다. 
  • 이 과정을 반복한 후, 배열에 남아있는 수는 소수이다.
• 많은 수의 소수를 한번에 판별하고자 할때 유용하다.
  • 많은 수의 소수를 반복문으로 구하게 되면 수행시간이 지나치게 길어질 수 있는데(시간복잡도 O(N²)), 에라토스테네스의 체는 반복하다보면 건너뛸 수 있는 소수가 아닌수들이 많아지기 때문에, 훨씬 빨리 소수를 판별할 수 있다.
• 시간복잡도는 O(NloglogN)으로 매우 빠르다.
• 단점: 소수를 판별해야 하는 범위 만큼의 크기를 가진 배열 생성이 필요하기 때문에 메모리가 많이 사용된다.

 

예를 들어 1~16을 확인한다고 할 때,

1은 소수가 아니므로 제외한다.

2부터 차례대로 살펴보면 2의 배수들을 모두 소수가 아니게 된다.

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

다음 소수인 3도 3의 배수들은 모두 소수가 아니게 된다.

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

즉, 소수의 배수는 소수가 아닌 점을 이용해서 소수를 찾는 알고리즘이다.

여기서 보면 2의 배수에서 4,6,8이 제거되기 때문에 3*2인 6도 이미 제거된 상태로 3의 배수를 볼 때, 3*3부터 보면 된다.

마찬가지로 5도 보면 5*2와 5*3은 이미 2의 배수와 3의 배수로 제거되었기 때문에, 5*5부터 보면 된다.

 

 

[구현코드 - JAVA]

50까지의 수 중 소수인 수 찾기

public class Study {
	
	public static void main(String[] args) {
		int N = 50;
		boolean[] check = new boolean[101];
		
		//소수는 false
		check[0]=true;
		check[1]=true;
		
		for(int i=2; i<=Math.sqrt(N); i++) {
			//이미 소수가 아닌수로 판별됐다면 
			if(check[i]) continue;
        
			//소수가 아닌 수 true로 변경
			//자기 자신 제외한 수 ex)i=2, j=4,6,8,10,...
			//i*i 이하의 수는 이미 검사했으므로 i*i부터 시작
			for(int j=i*i; j<=N; j+=i) { 
				check[j]=true;
			}
		}
		
		//소수 출력
		for(int i=2; i<=N; i++) {
			if(check[i]==false)
				System.out.print(i+" ");
		}
		
	}
}

//결과
//2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

첫번재 for문의 범위가 N이 아닌 Math.sqrt(N)인 이유는 N의 제곱근까지만 돌면 마지막은 N*N으로 N까지 볼 수 있기 때문이다.

원래 j=i+i로 구했었는데, 글로 정리하면서 보니 j=i*i로 해도 된다는 것을 알 수 있었다.