에라토스테네스의 체

에라토스테네스의 체

고대 그리스의 수학자인 에라토스테네스가 만들어 낸 소수를 찾는 방법

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

 

---

 

단일 숫자 여부를 확인 할 경우에는 특정한 숫자의 제곱근 까지만

약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.

수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다.

만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다.

 

에라토스테네스의 체

 

소수를 찾는 가장 간단하면서도 무식한 방법이다.

예를 들어 1부터 100까지 소수를 찾을때 1을 제외한 나머지 수 중에서

2를 소수로 분류하고 2의 배수를 다 지워준다.

3을 소수로 분류하고 3의 배수를 다 지워준다.

5를 소수로 분류하고 5의 배수를 다 지워준다.

7을 소수로 분류하고 7의 배수를 다 지워준다.

 

이런 식으로 남은 것들의 2배수, 3배수,...n배수를 지우다보면

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남는다.

이것이 100 이하의 소수이다.

이런 방법으로 만약 n이하의 소수를 모두 찾고 싶다면 1부터 n까지 쭉 나열한

다음 2의 배수, 3의 배수, 5의 배수...쭉쭉 나누는 것이다.

 

무식한 방법이지만 특정 범위가 주어진 후 그 범위 내에서 소수를 찾아야 하는 경우

에라토스테네스의 체 만큼 빠른 방법은 없다.

 

public class Eratos {
	public static void main(String[] args) {
		// ArrayList로 구현
		ArrayList<Boolean> primeList;

		// 사용자로부터의 콘솔 입력
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		// n <= 1 일 때 종료
		if(n <= 1) return;

		// n+1만큼 할당
		primeList = new ArrayList<Boolean>(n+1);
		// 0번째와 1번째를 소수 아님으로 처리
		primeList.add(false);
		primeList.add(false);
		// 2~ n 까지 소수로 설정
		for(int i=2; i<=n; i++ )
			primeList.add(i, true);

		// 2 부터  ~ i*i <= n
		// 각각의 배수들을 지워간다.
		for(int i=2; (i*i)<=n; i++){
			if(primeList.get(i)){
				for(int j = i*i; j<=n; j+=i) primeList.set(j, false);
				//i*i 미만은 이미 처리되었으므로 
                		//j의 시작값은 i*i로 최적화할 수 있다.
			}
		}
		StringBuffer sb = new StringBuffer();
		sb.append("{");
		for(int i=0; i<=n; i++){
			if(primeList.get(i) == true){
				sb.append(i);
				sb.append(",");
			}
		}
		sb.setCharAt(sb.length()-1, '}');

		System.out.println(sb.toString());

	}
}

// 자바로 구현