소수의 나열

어떤 정수 n에 대하여 아래의 조건을 만족하면 소수임을 알 수 있다.

2부터 n-1 까지의 어떤 정수로도 나누어 떨어지지 않는다.

그래서 처음 아래와 같은 프로그램을 작성한다면, 나눗셈을 하는 횟수가 너무 많아진다.

책에서는 위와 같은 문제를 해결하기 위해 아래와 같은 코드를 제시했다. 아래 알고리즘은 배열을 이용했고, 정수 n 이 소수이려면,

2부터 n-1 까지의 어떤 소수로도 나누어 떨어지지 않는다.

는 조건을 만족해야 한다는 아이디어를 바탕으로 하고 있습니다.

package chap02;
// 1,000 이하의 소수를 열거(버전 2)

class PrimeNumber2 {
    public static void main(String[] args) {
        int counter = 0;                        // 나눗셈의 횟수
        int ptr = 0;                            // 찾은 소수의 개수
        int[] prime = new int[500];                // 소수를 저장하는 배열

        prime[ptr++] = 2;                        // 2는 소수임

        for (int n = 3; n <= 1000; n += 2) {    // 대상은 홀수만
            int i;
            for (i = 1; i < ptr; i++) {            // 이미 찾은 소수로 나누어 봄
                counter++;
                if (n % prime[i] == 0)            // 나누어떨어지면 소수가 아님
                    break;                        // 더 이상의 반복은 불필요
            }
            if (ptr == i)                        // 마지막까지 나누어떨어지지 않음
                prime[ptr++] = n;                // 소수라고 배열에 저장
        }

        for (int i = 0; i < ptr; i++)            // 찾은 ptr개의 소수를  나타냄
            System.out.println(prime[i]);

        System.out.println("나눗셈을 수행한 횟수：" + counter);
    }
}

위 알고리즘으로 시행되는 나눗셈은 14,622회로 이전의 78,022회보다 훨씬 적다. 책(76p)은 다음과 같은 결론을 내린다.

1. 같은 답을 얻는 알고리즘은 하나가 아니다.
2. 빠른 알고리즘은 메모리를 많이 요구한다.

• 하나의 문제라도, 그 해결 방법은 천차만별이겠다. 단순 명쾌하면 좋겠지만 자신의 실력에 따라, 프로그램의 목적에 따라, 비용에 따라 맞는 알고리즘이 있을 것이다.
• 메모리의 경우, 아마 2번째 알고리즘에서 500개 짜리의 배열을 생성해서 그렇게 말한 것 같다.

그런데 책은 또다른 알고리즘 개선 방법을 제시해줬다. 이것은 정말 이해하기 어려웠다..

이 아이디어는 '약수의 대칭성'으로부터 얻을 수 있다. 예를 들어, 100 이 소수인지 판별한다고 하자. 100의 약수는 (2,50), (4,25), (10,10), (20,5), (25,4), (50,2) 로 (10,10)을 중심으로 대칭이다!

이는 정사각형 한 변의 길이까지만 소수로 나눗셈을 시도하고, 그 과정에서 한 번도 나누어 떨어지지 않으면 소수라고 판단해도 좋다는 것을 의미한다. (77p)

책에서는 위와 같이 말했는데 처음에는 전혀 이해하지 못했다..

100의 제곱근은 10이고, 1000의 제곱근은 10*10^(1/2)이다. 이 제곱근은 정사각형 한 변의 길이를 뜻하며, 정사각형 한 변의 길이보다 작은 소수들로'만' 나눗셈을 시도해도 소수 판별이 가능하다는 것이다!

왜냐하면 약수는 대칭성을 띠기 때문에, 제곱근 아래의 정수들(더 나눗셈을 적게 하려면 소수들)로만 나눠도 같은 결과가 나온다는 소리다.

정말로 그럴까?

예를 들어, 13과 15의 경우를 살펴보자.

• 13의 제곱근은 ‭3.605551275463989‬ 이다. 이 제곱근보다 작은 소수는 2와 3이다. 13을 2와 3으로 나눴을 때 나눠지지 않았다. 소수이다. 그리고 13은 소수가 맞다. (이렇게 증명하는 게 아닐텐데...)
• 15의 경우 제곱근은 ‭3.872983346207417‬ 이다. 15는 3으로 나눴을 때 나누어떨어진다. 소수가 아니다.

그래서 알고리즘을 개선한다면 어떻게 나올까? 책의 완성 파일을 가져와봤다.

package chap02;
// 1,000 이하의 소수를 열거(버전 3)

class PrimeNumber3 {
    public static void main(String[] args) {
        int counter = 0;                            // 곱셈과 나눗셈의 횟수
        int ptr = 0;                                // 찾은 소수의 개수
        int[] prime = new int[500];                    // 소수를 저장하는 배열

        prime[ptr++] = 2;                            // ２는 소수임
        prime[ptr++] = 3;                            // ３은 소수임

        for (int n = 5 ; n <= 1000; n += 2) {        // 대상은 홀수만
            boolean flag = false;
            for (int i = 1; prime[i] * prime[i] <= n; i++) {
                counter += 2;
                if (n % prime[i] == 0) {            // 나누어떨어지면 소수가 아님
                    flag = true;
                    break;                            // 더 이상의 반복은 불필요
                }
            }
            if (!flag) {                            // 마지막까지 나누어떨어지지 않음
                prime[ptr++] = n;                    // 소수라고 배열에 저장
                counter++;
            }
        }

        for (int i = 0; i < ptr; i++)                // 찾은 ptr개의 소수를 출력
            System.out.println(prime[i]);

        System.out.println("곱셈과 나눗셈을 수행한 횟수：" + counter);
        // 3774
    }
}

위 코드는 결국

어떤 정수 n은 'n의 제곱근' 이하의 어떤 소수로도 나누어떨어지지 않는다.

를 조건으로 하고 있고, for문의 제어식에 써야하는 'n의 제곱근 이하의 어떤 소수'를 쉽게 구하려면, '어떤 소수의 제곱'이 n 이하, 로 바꾸어 생각하면 편하다.

다음은 다차원 배열을 알아보도록 한다.

---

책 초반임에도 불구하고 생각할 거리가 많고 어렵다고 느껴진다. 하지만 그만큼 재밌고 새로운 것을 아는 쾌감이 있다.

꾸준히 배우고 익히자.