[알고리즘] 에라토스테네스의 체

에라토스테네스의 체 

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 소수를 찾기위해 만들어낸 방법으로,

 

마치 체를 치듯이 수를 걸러내기 때문에 에라토스테네스의 체라고 부른다.

 

'에라토스테네스의 체'로 소수를 구하는 방법은 2부터 시작해 하나의 수를 뽑고, 뽑은 수의 배수를 소수의 후보에서 제외시킨다.

 

에라토스테네스의 체 과정

만약, 1부터 10까지의 수 중 소수를 찾는다면

 

2부터 시작해서 2의 배수를 소수의 후보에서 제외시킨다.

 

2, 3, 4, 5, 6, 7, 8, 9, 10 (1은 소수가 아니므로 후보에서 제외)에서 2의 배수를 제거하면 2, 3, 5, 7, 9가 남는다.

 

2, 3, 5, 7, 9 에서 3의 배수를 제거하면 2, 3, 5, 7이 남는다.

 

이러한 방식으로 소수의 후보를 계속해서 제거하면, 남은 수들이 소수가 된다.

 

에라토스테네스의 체 구현

package samsung;

import java.util.*;

public class s_test {
	public static void main(String[] args) {
		int[] arr = new int[101];
		
		for(int i = 2; i < arr.length; i++) {
			int j = 2;
			while(i * j < arr.length) {
				arr[i * j] = 1;
				j++;
			}
		}
		for(int i = 2; i < 101; i++) {
			if(arr[i] == 0)
				System.out.print(i + " ");
		}
	}
}