[도구정리] 에라토스테네스의 체

에라토스테네스의 체는 소수를 판별해야할 때 매우 유리한 알고리즘이다. 

 

일반적오르 소수를 판별하는 방법은 1을 제외한 자기자신까지를 나눠보며 1과 자기자신으로만 나누어 떨어지는 것이 맞는지 확인하는 방법이다.

 

하지만 이는 매우 비효율적이다. 그럼 에라토스테네스의 체는 뭘까?

바로 제곱근보다 작은 숫자까지만 확인하면 된다는 것이다.

 

어떻게 가능할까?

 

예를 들어 120이라는 숫자가 소수인지 판별해보자. 제곱근은 루트120으로 11^2보다 작다.

즉, 우리는 10까지만 배수들을 지워가며 소수인지 아닌지 판별하면 된다는 것이다.

 

왜냐하면 10.xxxx * 10.xxxx 가 120이라는 숫자가 된다. 그 말은 120이라는 숫자를 만들기 위해서는 10.xxxx 를 하나는 숫자를 더 크게하고, 하나는 더 낮게 하는 방법밖에 없다는 것이다. 그러한 정수쌍을 찾아보면 가장 단순하게는 10*12가 된다.

그렇기 때문에 제곱근 이상의 숫자는 확인할 필요가 없는 것이다.

 

코드로 정리하면 다음과 같다

import java.io.*;

public class Algorithm {

    static boolean[] isPrime;
    
    static void isPrime_fun(int n){ 
        isPrime = new boolean[n+1]; // N번째의 수 까지 받기위해 N+1까지 동적할당
        
        for(int i = 0; i < isPrime.length; i++){
            isPrime[i] = true; // boolean배열의 default값은 false이므로 true로 바꿔주기
        }
        
        isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아니니깐 false
        
        for(int i = 2; i <= Math.sqrt(n); i++){ // 2부터 n의 제곱근까지의 모든 수를 확인
            if(isPrime[i]){ // 해당수가 소수라면, 해당수를 제외한 배수들을 모두 false 처리하기
                for(int j = i*i; j<= n; j += i){//그 이하의 수는 모두 검사했으므로 i*i부터 시작
                    isPrime[j] = false;
                }
            }
        }
    } // isPrime_fun 함수 종료

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 소수인지 판별할 숫자 input
        isPrime_fun(N);
    }
}