자바 코딩테스트 강좌, 소수 구하기

1. 문제 정의

많은 코딩 테스트 문제들은 수학적 개념이나 알고리즘적 사고를 요구합니다.
그 중 하나가 “소수 구하기”라는 문제입니다.
소수는 1과 자기 자신만을 약수로 갖는 자연수로 정의됩니다.
즉, 소수는 1보다 큰 자연수 중에서 1과 자기 자신 외에는 다른 약수를 갖지 않는 수입니다.
예를 들어, 2, 3, 5, 7, 11, 13, 17 등은 소수입니다.

이번 강좌에서는 주어진 정수 N 이하의 모든 소수를 출력하는 문제를 풀어 보겠습니다.
구체적으로 말하자면, “주어진 정수 N에 대해 N 이하의 모든 소수를 출력하라”는 문제가 됩니다.

2. 문제 예시

예제 입력: 20
예제 출력: 2, 3, 5, 7, 11, 13, 17, 19

3. 알고리즘 접근 방식

소수를 구하는 방법에는 여러 가지가 있습니다.
가장 단순한 방법은 2부터 N까지의 모든 수에 대해 각각 소수 여부를 확인하는 것입니다.
그러나 이 방법은 비효율적이며, O(N^2) 시간 복잡도를 가집니다.
따라서 우리는 더 효율적인 방법, 즉 에라토스테네스의 체 알고리즘을 사용할 것입니다.

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

에라토스테네스의 체는 소수를 찾기 위한 고전적인 알고리즘입니다. 이 방법의 기본 아이디어는 다음과 같습니다:

2부터 N까지의 모든 수를 나열합니다.
가장 작은 수인 2를 선택합니다. 2의 배수를 모두 지웁니다.
다음 남아있는 수 중에서 가장 작은 수를 선택합니다. 이 수가 소수입니다.
이 수의 배수를 모두 지웁니다.
이 과정을 N 이하의 수 중에서 소수가 남아있을 때까지 반복합니다.

4. 자바 코드 구현

이제 에라토스테네스의 체 알고리즘을 자바로 구현해 보겠습니다.
아래는 구현 코드입니다:


import java.util.ArrayList;
import java.util.List;

public class PrimeNumbers {
    public static void main(String[] args) {
        int N = 20; // 여기서 N의 값을 바꿔서 다른 범위의 소수를 찾을 수 있습니다.
        List<Integer> primes = findPrimes(N);
        System.out.println("소수(" + N + "이하): " + primes);
    }

    public static List<Integer> findPrimes(int N) {
        boolean[] isPrime = new boolean[N + 1];
        List<Integer> primes = new ArrayList<>();

        // 0과 1은 소수가 아니므로 false로 초기화
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false; // i의 배수를 소수 후보에서 제외
                }
            }
        }

        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) {
                primes.add(i); // 소수 리스트에 추가
            }
        }
        return primes;
    }
}

5. 코드 설명

위의 코드에서는 다음과 같은 단계로 소수를 구합니다:

배열 초기화: isPrime이라는 불리언 배열을 생성하여
0에서 N까지의 수가 소수인지 여부를 저장합니다. 초기에는 모든 수를 소수로 가정하고 시작합니다.
소수 판별: 이중 루프를 사용하여 각 수의 배수를 지워 나갑니다. 외부 루프는 소수 후보 수를,
내부 루프는 이 소수의 배수를 지웁니다.
소수 목록 생성: 마지막으로, 소수 판별이 끝난 후,
isPrime 배열을 확인하여 실제 소수인 수를 리스트에 추가합니다.

6. 코드 실행 결과 설명

위 코드를 실행하면 주어진 N 값에 대한 소수 목록을 출력합니다. 예를 들어, N이 20이면 다음과 같은 결과를 출력합니다:
소수(20이하): [2, 3, 5, 7, 11, 13, 17, 19]

7. 성능 최적화

에라토스테네스의 체 알고리즘은 O(N log log N)의 시간 복잡도를 가지며, 매우 효율적입니다.
그러나 N이 매우 클 경우에는 메모리 사용량도 고려해야 합니다.
그래서 메모리를 절약하기 위한 몇 가지 방법은 다음과 같습니다:

짝수는 2를 제외하고는 소수가 아니므로, 홀수만을 대상으로 소수를 탐색할 수 있습니다.
배열 대신 비트 벡터를 사용할 수 있어 메모리 사용량을 줄일 수 있습니다.
대칭을 이용하여 N의 제곱근까지만 탐색하면 됩니다. 즉, 소수가 아닌 수를 찾는 작업을 제곱근까지만 수행하고,
나머지 수는 소수가 아닐 것이므로 이를 저장할 필요가 없습니다.

8. 마무리

이번 강좌에서는 자바를 이용하여 소수를 구하는 방법을 알아보았습니다.
에라토스테네스의 체 알고리즘은 소수를 구하는 데 있어서 매우 효율적이며,
이러한 알고리즘의 이해는 코딩 테스트에서 유용하게 쓰일 것입니다.
추가적으로, 다수의 고차원 알고리즘 문제를 해결하기 위해 알면 도움이 되는 기본적인 수학적 사실들 외에도
다양한 자료구조와 알고리즘에 대한 이해를 증진시키는 것도 중요합니다.

다음 시간에는 더 다양한 알고리즘 문제를 다뤄 보도록 하겠습니다.
코딩 테스트 준비에 도움이 되길 바랍니다!