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

소수 개념 정의

 

• 소수
  • 1과 자기 자신 이외에는 나누어 떨어지지 않는 자연수이다

• 약수
  • 어떤 수를 나누어 떨어지게 만드는 수를 그 수의 약수라고 한다.
  • 예를 들면, 6의 약수는 1, 2, 3, 6이다.
• 합성수
  • 1과 자기 자신 외에도 다른 약수를 갖는 자연수를 말한다.
  • 합성수는 항상 두 개 이상의 약수를 가지므로, 소수와 대조된다.
  • 예를 들면, 4, 6, 8 ... 등은 모두 합성수이다.

 

 

---

 

소수 판별 알고리즘

 

코드

 

public static boolean isPrime(int number) {

    // 1은 소수가 아니다
    if (number==1) return false;

    // √number 까지 반복
    for(int i=2; i<=Math.sqrt(number); i++){
        if(number % i == 0) return false;
    }

    return true;
}

 

소수 판별 알고리즘을 검색하면 자주 나오는 시간복잡도 O(√n) 인 코드이다.

하지만 왜 √n 까지 체크하면 되는지 설명하는 곳은 많지않아서 증명을 정리했다.

 

 

증명

 

우리가 증명하고 싶은건 n 이 합성수라면 √n 보다 작은 약수를 가진다는 사실이다. 

 

이를 부정하는 명제를 하나를 들어보자.

 

명제 : n이 합성수이면 √n 보다 작거나 같은 약수를 갖지않는다.

 

• n = a*b  (2≤a≤b<n)
  
  • n은 임의의 a, b의 곱으로 나타낼 수 있다.
  • n 이 합성수이기 때문에 (2≤a≤b<n) 조건이 필요하다. (위에 합성수 정의 참고)
• √n < a, √n < b
  
  • √n 보다 작거나 같은 약수를 갖지않기 때문 (명제)
• √n * √n < a * b
• n < a * b
• n < n (거짓 판결)

 

결론 : n 이 소수가 아니라면 n의 약수 중에서 √n 보다 작거나 같은 소수가 존재한다.

 

자연수 n이 √n 이하의 어떤 소수로도 나누어 떨어지지 않으면 n은 소수라는 사실을 바탕으로 계산하면 된다.

 

 

---

 

에라토스테네스의 체

 

특정 범위 내의 모든 소수를 효율적으로 찾는 방법으로 에라토스테네스의 체를 많이 사용하는데 시간복잡도가 O(n * log(log n)) 으로 매우 효율이 좋은 알고리즘이다. 
이 알고리즘은 자연수의 배열에서 소수가 아닌 수를 걸러내어 남은 수들만 소수로 확인하는 방식으로 작동한다.

 

 

설명

어떤 수의 배수는 소수가 될 수 없다는 점을 이용하여 수의 범위 내에서 소수만 남도록 체로 거른다.

에라토스테네스의 체는 2부터 시작하여 소수의 배수를 하나씩 제거해 나가는 방식으로 소수를 판별하는 과정을 통해 소수가 아닌 수들은 제거해서 소수를 남긴다. 

 

 

과정

• 1을 제외한 자연수 2부터 N까지 나열한다.
• 소수 판별
  • 첫 소수인 2부터 시작
  • 현재 숫자를 p(소수)라 할 때, p의 배수를 나열한 자연수에서 제거
  • 제거되지 않은 다음 수를 p로 지정후 반복
• 제곱근까지 반복: p가 √n보다 작거나 같을 때까지 소수 판별 과정을 반복한다.
  • √n보다 큰 수의 배수는 이미 소수의 배수로 지워졌기 때문에 √n 까지 반복한다. (위 증명 참고)
• 나열된 남은수는 소수이다.

 

 

예시

2~100 범위의 소수 판별 예시

 

 

 

코드

import java.util.Arrays;

public class SieveOfEratosthenes {

    // 에라토스테네스 체 알고리즘
    public static boolean[] sieve(int N) {

        // isPrime[n] 값이 n이 소수인지 아닌지 판별할 수 있게 배열 크기를 N+1 로 정의
        boolean[] isPrime = new boolean[N + 1];

        // isPrime 배열을 모두 true 로 초기화
        Arrays.fill(isPrime, true);

        // 0과 1은 소수가 아니므로 false로 설정
        isPrime[0] = false;
        isPrime[1] = false;

        // 2부터 n의 제곱근까지 반복
        // 자연수 n 까지의 소수는 √n 범위 내에서 판별 가능
        for (int num = 2; num <= Math.sqrt(N); num++) {

            // num 이 소수인 경우, num 의 배수들을 false 로 설정
            if (isPrime[num]) {
                for (int multiple = (int) Math.pow(num, 2); multiple <= N; multiple += num) {
                    isPrime[multiple] = false;
                }
            }
        }

        return isPrime;
    }

    public static void main(String[] args) {

        // 자연수 n 까지의 모든 소수를 구함
        int n = 100;

        // n 이하 자연수를 에라토스테네스 체로 거르기
        boolean[] isPrime = sieve(n);

        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

 

 

---

 

 

출처

소수 판별 이미지 : https://commons.wikimedia.org/wiki/File:Sieve_of_Eratosthenes_animation.gif

증명 참고 : https://fl0ckfl0ck.tistory.com/258