에라토스테네스의 체 : 소수 판정

dev-jjun·2023년 2월 17일

알고리즘

Algorithm

목록 보기

14/15

소수란?

1보다 큰 자연수 중 1과 자기자신만을 약수로 가지는 수

에라토스테네스의 체

대량의 소수를 한꺼번에 빠르고 정확하게 판별할 수 있는 알고리즘으로, 가장 먼저 소수를 판별할 범위만큼 배열을 할당하고, 해당 값을 넣어준 후 하나씩 지워나가는 방식이다.

마치 체처럼 걸러낸다고 하여 다음과 같은 이름이 붙었고, 2부터 시작하여 특정 수의 배수에 해당하는 수를 배열에서 지워내고 남아있는 수를 소수로 판정한다.

소수 구하기 알고리즘

1. 나누어떨어지는 수의 여부 체크

주어진 수에 대해 2부터 (자기자신-1)로 나누어 떨어지는 수가 하나라도 있다면 그 수는 소수가 아니다. 하지만 이는 처음부터 반복문을 돌아야 하므로 나누어 떨어지는 수가 큰 수일수록 속도가 저하된다.

2. 제곱근 사용

1번 방식의 단점을 보완하고자, 소수의 수학적 성질을 이용하면 주어진 수의 제곱근까지만 나누어 떨어지는지 검사한 결과와 동일하다. 나누는 수에서 쌍을 이루지 않는 수가 존재할 때 그 최대는 N*N 즉, 제곱근이므로 제곱근까지만 판별할 경우 복잡도는 1차에서 절반만큼 줄어들게 된다.

3. 에라토스테네스의 체 원리 이용

1,2번 방식은 단일 숫자에 대한 소수를 판정할 때 사용하고, 1~N까지의 수에서 모든 소수를 구하고자 할 때는 ‘에라토스테네스의 체’ 원리를 사용할 수 있다.

public class PrimeNumber {
    public static void main(String[] args) {

        int maxNum  = 100000;   // 판별할 대량의 소수 중 최댓값

        // 1. 배열 생성 후 초기화
        int[] arr = new int[100001];
        for (int i=2; i<=maxNum; i++) {
            arr[i] = i;
        }

        // 2. 2부터 시작하여 특정 수의 배수에 해당한다면 배열에서 지운다.(0으로 변경)
        for (int i=2; i<=maxNum; i++) {
            if (arr[i] == 0) continue;   // 이미 지워진 수라면 건너뛰기

            // 이미 지워진 숫자가 아닌 경우, 그 배수부터 건너뛰어서 시작
            for (int j=2*i; j<=maxNum; j+=i) {
                arr[j] = 0;
            }
        }

        // 3. 2부터 남아있는 수를 모두 소수라고 판별한다.
        for (int i=2; i<=maxNum; i++) {
            if (arr[i] != 0)
                System.out.println(arr[i]);
        }
    }
}

*빠른 소인수분해

위 방식을 이용하면, 특정 수의 소인수분해를 아주 빠르게 구현할 수 있다.

//== 특정 수의 소인수분해 ==//
int n = 30;   // 30을 소인수분해 해보자!
for (int i=0; n>1; i++) {
    if (arr[i] != 0) {   // 해당 수가 소수인 경우
        while (n % i == 0) {
            System.out.println(i);  // 30의 소인수(소수)
            n /= i;   // 다시 그 수를 소수로 나눈 후에 다시 반복
        }
    }
}