소수판별법 - 에라토스테네스의 체

|  합성수와 소수

합성수	나누어떨어지는 수가 하나라도 존재하는 수	ex. 100 = 1 x 100, 2 x 50, 4 x 25, 5 x 20, 10 x 10...
소수	오직 1과 자기 자신만으로 나누어떨어지는 수	ex. 3 = 1 x 3

 

소수에 관한 알고리즘 문제는 보통 아래의 세가지가 있다고 하는데요.

 

1. 자연수 N이 소수인지 판별하거나, 

2. 1~N까지 중 소수의 갯수를 구하거나

3. 1 ~ N 까지의 소수를 나열하는

 

이 중에서 먼저 1.자연수 N이 소수인지 판별하는 법을 이야기해 보려고 합니다.

 

|  N을 2부터 N - 1 까지 모두 나누기

[1] 소수는 1과 자기 자신을 제외한 다른 수로는 나누어떨어져서는 안됩니다. 

 

그것을 판별하기 위한 코드는 아래와 같은데요. 2부터 N - 1가 N의 약수인지 확인하는 과정입니다.

public static boolean solution(int n) {

    // 1은 소수가 아니다.
    if (n == 1) {
        return false;
    }

    for (int i = 2; i < n; i++) { 
        if ((n % i) == 0) {
           return false;
        }
    }

    return true;
}

 

[2] 여기에서 합성수의 성질을 이용해 2 ~ N - 1이 아닌 2 ~ 루트N까지로 소수 여부를 확인할 수 있어요.

 

- 예를 들어, N이 100이라고 할 때, 1과 자기자신인 100을 제외한 약수를 구하면 아래 표와 같아요.

- 보면 10 x 10 을 전후로 a x b 가 b x a로 바뀌는 걸 볼 수 있습니다.

- 우리는 N이 합성수가 아닌지를 보려는 것이므로, 루트N까지 a가 있는지 확인하면 됩니다.

 

2x50

4x25

5x20

10x10

20x5

25x4

50x2

 

- 그럼 코드는 아래와 같이 변경됩니다.

public static boolean solution(int n) {

    // 1은 소수가 아니다.
    if (n == 1) {
        return false;
    }

    for (int i = 2; i <= (int)Math.sqrt(n); i++) { 
        if ((n % i) == 0) {
           return false;
        }
    }

    return true;
}

 

이번에는 2. 1~N까지 중 소수의 갯수를 구하는 법을 얘기하려 합니다.

2.3. 1 ~ N까지 범위의 소수의 갯수나 소수 나열을 위한 알고리즘은 여러가지가 있으나

그 중에서도 가장 많이 사용되는 것이 에라토스테네스의 체라고 해요.

 

|  에라토스테네스의 체

- 소수는 2가 아닌 짝수가 나올 수가 없습니다.

- 그리고, 각 소수 2, 3, 5, 7의 배수면 소수가 아니죠.

- 에라토스테네스는 체에 거르듯이 소수가 아닌 수들을 거르는 알고리즘을 말합니다.

 

에라토스테네스의 체 알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

출처 : 위키백과

 

- 코드는 그러면 아래와 같이 나옵니다.

public static int solution(int n) {

    int[] numArr = new int[n];

    // 1로 초기화 (0, 1 제외)
    for (int i = 2; i < n; i++) {
        numArr[i] = 1;
    }

    // 2 ~ 루트n까지의 수들이 N의 약수인지 확인한다
    for (int i = 2; i <= (int)Math.sqrt(n); i++) {
        if (numArr[i] == 0) continue; // 이미 검사된 수 건너띄기

        // 자기자신을 제외한 모든 i의 배수 제외
        for (int j = i * 2; j < n; j+=i) { // i : 3, j : 6, 9, 12
            numArr[j] = 0;
        }
    }

    return Arrays.stream(numArr).sum();
}

 

 

[참조]

https://rebro.kr/46?category=449699 

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