소수 알고리즘 - 제곱근 & 에라토스테네스의 체 이용

소수는 1과 자기 자신으로만 나누어는 수이다.

 

 

예로 100을 들어보자.

 

100은 1, 2, 4, 5, 10, 20, 25, 50, 100 으로 나누어질 수 있다.

 

100의 제곱근 10을 기준으로 대칭이 되는 것을 확인할 수 있다.

1 * 100   /   2 * 50   /   4 * 25   /   5 * 20

 

 

여기서, 1은 모든 수의 약수이므로 제외하고, 제곱근 이전의 수들은 제곱근 이후의 수들과 대칭되므로

나눠지는 수들을 모두 체크할 필요없이, 제곱근 이전의 수들로만 체크해보면 된다.

 

 

결론은,

2부터 제곱근까지 나누어봤을 때, 나눌 수 있는 수가 단 1개도 존재하지 않으면 그 수는 소수이다.

 

예시로, 인자로 들어간 수가 소수인지 판별하는 메서드를 구현해보았다.

 

 

이렇게 제곱근을 이용하면, 모든 수를 둘러보지 않아도 되는 장점이 있다.

 

 

 

 

또 다른 대표적인 소수 알고리즘의 풀이법으로 '에라토스테네스의 체'를 이용한 방법이 있다.

소수가 되는 수의 배수를 지우면 남는 건 소수이다. 2부터 자기 자신을 제외한 배수가 되는 것을 지우면 된다.

 

 

위키백과에 나온 에라토스테네스 체의 원리는 다음과 같다.

 

에라토스테네스의 체

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 소수가 되는 수의 배수를 지우면 남는 건 소수 뿐이다.
3. 자기 자신을 제외한 2의 배수를 모두 지운다. // 2
4. 남아 있는 수 중에서 자기 자신을 제외한 3의 배수를 모두 지운다. // 2, 3
5. 남아 있는 수 중에서 자기 자신을 제외한 5의 배수를 모두 지운다. // 2, 3, 5
6. 위 과정을 반복한다. // 2, 3, 5, 7, 11, ...

 

 

 

원리만 보면 잘 이해되지 않을 수 있다.

프로그래머스 '소수 찾기' 문제의 풀이 코드를 보며 이해해보자.

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

(인자로 받는 n까지의 수들 중 소수의 개수를 반환하는 문제)

 

 

- 풀이 코드

class Solution {
    public int solution(int n) {
        int[] arr = new int[n+1];
        int cnt = 0;
        
        for (int i = 2; i <= n; i++) {
            if (arr[i] == 0) {
                cnt++;
            }
            
            for (int j = i; j <= n; j += i) {
                arr[j] = 1;
            }
        }
        
        return cnt;
    }
}

 

1. 일단, 인자로 받는 n의 +1한 만큼의 배열을 생성해준다.
   이는 인덱스가 0으로 시작하는 배열의 특성상 숫자를 맞춰주기 위함이다.
   배열을 생성하면, 초기 배열 안의 값들은 모두 0일 것이다.
2. 이제 2부터 n까지 배열을 순회한다.
   2부터 순회하는 이유는 0, 1은 소수가 될 수 없기에 배제하고 가는 것이다.
3. 처음 인덱스 2인 곳부터 시작하면, 당연히 0이기에 cnt는 1 증가하게 된다.
   그 이후, 2번째 for문에서 현재 인덱스(2)부터 n까지 해당 인덱스의 배수들을 모두 1로 초기화한다.
4. 이 과정이 '에라토스테네스의 체'이다. 체를 거르듯, 한 숫자의 배수들을 모두 거르는 것이다.
5. 배열 안의 값이 0일 경우만 cnt(소수의 개수)는 증가될 것이기 때문에, 소수만 골라 세줄 수 있다.

 

 

 

요약하자면, 소수를 찾는 알고리즘, 소수의 갯수를 구하는 알고리즘 등 소수와 관련된 문제에서는 풀이법이 대표적으로 크게 2가지이다. '제곱근 방식' & '에라토스테네스의 체'

 

같은 문제를 두 방법으로 풀어본 결과, 에라토스테네스의 체를 사용한 방식이 좀 더 빨랐다.

소수 관련 알고리즘에는 에라토스테네스의 체를 이용하는 것이 더 좋겠다.

 

 

 

 

Ref)

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

https://kyeahen.github.io/algorithm/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-12921-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0/