[JAVA] 소수 알고리즘

Ureca.·2024년 10월 9일

우리가 처음 소수(Prime Number)를 배우는 시기는 중학교이다. 그 때 이 소수를 어떻게 정의했었냐면 다음과 같다.

1보다 크면서 1과 자기 자신만을 약수로 갖는 자연수

그래서 우리는 그 시절 자연수는 1, 소수, 합성수로 구분할 수 있었죠.
이제 개발자로서 코딩테스트를 위해 기초적으로 코딩을 해야하는 것중에 소수 구현이 있습니다. 이 소수를 자바로 구현해보고자 합니다.

에라토스테네스의 체

중학생 때 그래도 졸지 않았다면, 이 에라토스테네스의 체는 어떻게 구현하는지 알 수 있죠.

그 시절에는 1부터 50까지 칸을 작성한 다음에 다음과 같은 순서로 숫자를 지워나갔습니다.
1. 1을 지운다.
2. 2와 이에 해당하는 배수를 지운다.(짝수)
3. 3을 제외한 3의 배수를 지운다.
4. 5를 제외한 5의 배수를 지운다.
5. 7을 제외한 7의 배수를 지운다.
... 해당 순서를 반복하게 되며 제가 지정한 N. 즉, 50까지 이 순서를 진행하면 소수만 적혀있는 표가 완성이 됩니다.
💕주요 알고리즘은 다음과 같습니다.

주요 알고리즘

        for (int i = 2; i * i <= num; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= num; j += i) {
                    isPrime[j] = false;
                }
            }
        }

첫 번째 for 반복문

i는 현재 소수 후보
i = 2부터 시작해, i가 $\sqrt{num}$ 이하일 때까지 반복합니다.
- 예로, num이 30이라면, i는 5까지 반복하게 될 것입니다.
- 이렇게 구현을 하는 이유는, 어떤 num의 소수를 판별할 때, $\sqrt{num}$ 보다 큰 수들은 이미 그 이전의 소수의 배수로 판단이 됐기 때문입니다. 이는 위에서 소수를 제외한 그에 따른 배수를 지우는 것과 일맥상통합니다.
- 예로, 30의 경우에는 2, 3, 4, 5의 배수를 검사하면 다 걸러집니다.
i가 소수인지 확인하기 위해 if(isPrime[i]) 조건을 사용합니다.
- true라면, i는 소수입니다.

두 번째 for 반복문

j는 소수 i의 배수를 의미합니다.
- j의 초기값은 i * i로 설정됩니다.
- 예로, i = 3일 때, j는 3 * 3 = 9에서 시작하고, 그보다 작은 배수 3 * 2 = 6 은 이미 i = 2일 때 처리했습니다.
j의 증가값은 i입니다.
- i = 3일 때, j = 9, 12, 15, ...이 되며, 이는 i의 배수를 false로 설정해 소수가 아님을 표시합니다.
- j <= num 조건이 충족할 때까지 반복하게 됩니다.

핵심 알고리즘 정리

첫 번째 반복문은 현재 소수 후보를 결정하고, 그 소수의 배수들을 두 번째 반복문에서 제외합니다.
i가 소수라면 i * i부터 시작해 i의 모든 배수(i * i, i * i + i, i * i + 2i, ...)를 false로 설정합니다.
따라서 이미 isPrime[j]가 false로 설정된 숫자는 이전에 작은 소수들의 배수로 표시가 되었기 때문에 반복문에서 스킵합니다.

최종 코드


import java.io.*;
import java.util.*;

public class Main_에라토스테네스의체 {

    static void findPrimes(int num) {
        // 소수 찾기
        boolean[] isPrime = new boolean[num + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false; // 0은 소수가 아니다.
        isPrime[1] = false; // 1은 소수가 아니다.

        // 2부터 시작하여 배수를 제거.
        // i는 소수 후보.
        for (int i = 2; i * i <= num; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= num; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        // StringBuilder를 사용하여 출력 최적화
        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= num; i++) {
            if (isPrime[i]) {
                sb.append(i).append(" ");
            }
        }
        // 최종 출력
        System.out.println(sb.toString().trim());
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        findPrimes(n);
    }

}