Algorithm - Sieve of Eratosthenes(소수판별 알고리즘)

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

고대 그리스 수학자 에라토스테네스의 가장 대표적인 소수(Prime Number) 판별 알고리즘. 마치 체로 수를 걸러낸다고 해서 에라토스테네스의 체 라고 부름. 소수들을 대량으로 빠르고 정확하게 구하는 방법. 소수는 양의 약수를 두개만 가지는 자연수(2, 3, 5, 7, 11, ... 등).

 

모든 경우의 수를 다 돌며 약수 여부를 확인하는 경우 시간 복잡도 => O(N). 매우 비효율적. 

-> 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 됨. (ex. 8 = 2 * 4 = 4 * 2). => O(N^(1/2))

-> 한 두개의 소수를 판별하는 게 아닌 대량의 소수를 한꺼번에 판별하고자 할 때 사용하는 것이 바로 에라토스테네스의 체

즉, 어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있음. 어떤 수가 수를 나누면 몫이 생기는데 몫과 나누는 수 둘중 하나는 N제곱근 이하이기 때문. 

 

에라토스테네스의 체의 원리 :

1. 배열을 생성하여 초기화. (소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용)

2. 2부터 시작해서 특정 배수에 해당하는 수를 모두 지움. (소수도 합성수도 아닌 유일한 자연수 1을 제거 -> 2를 제외한 2의 배수 제거 -> 3을 제외한 3의 배수 제거 -> 4의 배수는 2의 배수에서 지워졌으므로 지울필요 x -> 5를 제외한 5의 배수 제거 -> 7을 제외한 7의 배수 제거 / 지울때 자기자신은 지우지 않음. 이미 지워진 수는 건너뜀)

3. 2부터 시작해서 남아있는 모든 수 출력

 

-> 무식한 방법이지만 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우 아직까지 소수들 간의 연관성(소수를 생성할 수 있는 공식)이 나오지 않았으므로 에라토스테네스의 체보다 빠른 방법이 없다고 함. / 하지만 특정 범위 내의 소수를 판정하는 데에만 효율적. 만약 숫자 하나가 주어지고 이것이 소수인가를 따진다면 소수판정법이라는 에라토스테네스의 체보다 빠른 방법이 있다고 함. 또한 에라토스테네스의 체로 특정 범위 n까지의 소수를 알고 싶을 때, n까지 모든 수의 배수를 나눠 볼 필요 x. 만약 n보다 작은 어떤 수 m이 m = ab라면 a와 b 둘중 하나는 루트n 이하임. 즉 n보다 작은 합성수 m은 루트n보다 작은 수의 배수만 체크해도 전부 지워진다는 의미. 

 

public class Eratos {
	public static void main(String[] args) {
    	ArrayList<Boolean> primeList;
        StringBuffer sb = new StringBuffer();
        
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        
        if (n <= 1) return;
        
        primeList = new ArrayList<Boolean>(n+1); // n+1 만큼 할당 후 0과 1을 소수 아님으로 처리
        primeList.add(false);
        primeList.add(false);
        
        for (int i = 2; i < n; i++) 
        	primeList.add(i, true);
        
        for (int i = 2; i*i < n; i++) {
        	if (primeList.get(i)) {
            	for (int j = i*i; j <= n; j+=i) // i*i 미만은 이미 처리됬으므로 시작값은 i*i로 최적화함.
                	primeList.set(j, false);  
            }
        }
    	
        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());
    }
}