[알고리즘] 소수 구하기, 에라토스테네스의 체

에라토스테네스의 체

• 소수를 구하는 방법 중 하나 
• i = 2 부터 √N 이하까지 반복하여 자연수들 중 i를 제외한 i의 배수들을 제외시키는 방식
• 시간복잡도: O(Nlog(log N))

에라토스테네스의 체

 

다음의 그림과 같이 1을 제외하고 2부터 시작하여

2의 배수인 4, 6, 8, 10 .. 는 이미 2를 약수로 가져 소수가 아니므로 제외하고

그 후 3의 배수인 9, 15, 21, 27 .. 들도 이미 3를 약수로 가져 소수가 아니므로 제외하면서 범위 내 소수를 구하는 방식이다. 

 

 

왜 N 까지가 아니라  √N 까지일까?

n = a × b 라고 하고 하면 1 ≤ a, b < n 이 성립한다. 만약 a, b가 n의 제곱근보다 커지면 모순이 발생한다.

그래서 만약 a, b > √ N 하다면 a × b > n 이므로 a와 b 중 적어도 하나는 n의 제곱근보다 작거나 같다.

 

쉽게 말해, 소수인지 판별 할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나기 때문이다.

 

 

코드

N 이하의 모든 소수를 구하라.

public class sifter {
    public static boolean[] prime;	// 소수를 체크할 배열
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        Prime(N);

        for(int i = 0; i < prime.length; i++) {
            if(prime[i] == false) {	// 소수(false)일 경우 출력
                System.out.println(i);
            }
        }
    }

    // N 이하 소수 생성 메소드 
    // 소수면 false, 소수가 아니면 true
    public static void Prime(int N) {
        prime = new boolean[N + 1];	 // 0 ~ N
        prime[0] = prime[1] = true;  // 숫자 0과 1은 소수가 아님
        
        if(N < 2)  // N이 1 이하일 경우
            return;

        // √N(제곱근) 이하까지 반복 
        for(int i = 2; i <= Math.sqrt(N); i++) {
            if(prime[i] == true)  // 이미 한번 체크된 배열이면 continue
                continue;

            // i의 배수라면 소수가 아니므로 true
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

 

자연수 N 크기만큼의 boolean 배열을 만들어 준다. 이때 boolean 배열의 초기값으로는 false이라 전체가 다 false가 되어있지만 후에 소수가 아닌 숫자들을 처리할 때 true로 만들어 주어 소수가 아니면 true, 소수이면 false가 되도록 boolean 배열을 수정한다.

 

그리고 boolean 배열이 다 만들어지면 해당 숫자가 소수인 지 소수가 아닌 지 boolean 배열의 index로 해당 숫자를 넣었을 때 그 결과가 소수가 아니면 true, 소수이면 false로 나오게 된다.