[Algorithm] 소수 구하기

백준 1929 : 소수 구하기

🏆 문제 설명

자연수 M 이상 N 이하의 모든 소수를 구하는 문제입니다.

---

💡 접근 방법

• 2부터 √N까지의 수로 나누어 떨어지는지 확인하여 소수를 판별합니다.
• 범위 내의 모든 소수를 출력해야 하므로 에라토스테네스의 체를 활용하는 것이 효율적이지만, 시간 복잡도를 계산했을 때 최대 1,000,000의 O(√N) 이므로 시간 제한이 널널합니다. 따라서, 단순히 나누어 떨어지는지 확인하는 방법으로 해결해보겠습니다.

💻 코드 (기본적인 소수 판별)

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        for (int i = N; i <= M; i++) {
            if (isPrime(i)) {
                System.out.println(i);
            }
        }
    }

    public static boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

🧐 회고

• 예전에 한 번 풀어본 적이 있어서 어렵지 않게 해결했다.
• 하지만, 범위가 커질 경우 O(√N) 방식으로 모든 숫자를 검사하는 것은 비효율적일 수 있다.
• 그때는 에라토스테네스의 체 를 적용하여 더 빠르게 풀 수도 있다.

🚀 추가 개선: 에라토스테네스의 체 적용

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        boolean[] isPrime = new boolean[M + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

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

        StringBuilder sb = new StringBuilder();
        for (int i = N; i <= M; i++) {
            if (isPrime[i]) sb.append(i).append("\n");
        }
        System.out.print(sb);
    }
}