📊 Algorithm/BOJ

🧪백준 1929 - 소수 구하기

hjwjo 2025. 1. 7. 20:28

https://www.acmicpc.net/problem/1929

백준(BOJ) 사이트에 들어간 게 정말 오랜만이네요.

최근에 바쁘다는 핑계로 알고리즘 문제 풀이에서 많이 멀어졌던 것 같습니다.

이제부터라도 하루에 한 문제씩 가벼운 문제를 풀고,

일주일에 한 번씩은 좀 더 복잡한 알고리즘 문제도 도전해서 감을 잃지 않도록 꾸준히 유지해보려고 해요.

물론 매일같이 문제를 푸는 게 쉽지는 않겠지만, 틈틈이 하루에 한 문제씩 일반 문제를 풀고 ,

일주일에 한 문제씩 알고리즘 문제를 풀어볼려고 목표를 설정했습니다.

 

문제 설명

  • 문제
    M이상 N이하의 소수를 모두 찾아서 출력해야 합니다.
  • 입력
    • 한 줄에 자연수 M과 N이 주어집니다. (1 ≤ M ≤ N ≤ 1,000,000)
    • M 이상 N 이하의 소수가 하나 이상 존재하는 입력만 주어집니다.
  • 출력
    • M 이상 N 이하의 소수를 오름차순으로 한 줄에 하나씩 출력합니다.

예제

  • 입력 
    3 16
  • 출력 
    3
5
7
11
13

단순 반복(브루트포스) 

처음에는 각 숫자가 소수인지 판별하는 메서드를 만들고 , M부터 N까지 전체를 검사하려고 했습니다.
x에 대하여 2부터 √x(x의 제곱근)까지 나눠보면서 한 번이라도 나누어떨어질 때 소수가 아니라고 판정하도록

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public 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 M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        
        // M부터 N까지 순회하며 isPrime 판별
        StringBuilder sb = new StringBuilder();
        for (int i = M; i <= N; i++) {
            if (isPrime(i)) {
                sb.append(i).append("\n");
            }
        }
        
        System.out.print(sb);
    }
    
    // 소수 판별 메서드
    private static boolean isPrime(int num) {
        // 1은 소수가 아니므로 바로 false
        if(num <= 1) {
            return false;
        }
        
        // 2부터 sqrt(num)까지 나눠떨어지면 소수가 아님
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}
  • 작동 원리
    • M부터 N까지 모든 숫자 i에 대해, isPrime(i)를 호출합니다.
    • isPrime(i) 내부에서는 2부터 sqrt(i)까지 돌며 나누어떨어지는지 확인합니다.
  • 시간 복잡도
    • 최악의 경우 N−M+1N - M + 1개에 대해 각각 N\sqrt{N}까지 검사
    • 대략 O((N−M+1)N)O((N-M+1)\sqrt{N})
  • 결과: NN이 최대 1,000,000까지 가능하므로, 최악의 경우 1,000,000에 가까운 수를 검사해야 하고 각 수마다 최대 1,000번 정도(루트 1,000,000 ≈ 1000) 반복하게 됩니다. (문제는 풀 수 있었으나 , 시간이 오래걸리는 단점 )

"에라토스테네스의 체" -  Algorithm

큰 범위에서 소수를 빠르게 구하는 대표적인 알고리즘은 에라토스테네스의 체(Sieve of Eratosthenes)입니다.

알고리즘 아이디어

  1. 2부터 시작해서, 어떤 수 i가 소수라고 판단되면 i의 배수들을 모두 소수가 아니라고 표시
  2. 그 다음 수로 넘어가서, 여전히 소수로 표시되어 있다면 또 그 배수를 지움
  3. 이를 반복하면, 결과적으로 소수가 아닌 숫자는 전부 필터링

시간 복잡도

  • 에라토스테네스의 체는 대략 O(Nlog⁡log⁡N)O(N \log \log N)의 시간 복잡도를 가집니다.
  • NN이 1,000,000이라도 충분히 2초 내에 계산 가능하므로, 시간 초과를 해결할 수 있습니다.

에라토스테네스의 체 코드 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public 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 M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        
        // 인덱스를 숫자로 보고 해당 숫자가 소수인지 여부를 저장할 배열
        boolean[] isPrime = new boolean[N + 1];
        
        // 2부터 N까지 일단 모두 소수(true)라고 가정 (단, 0과 1은 소수가 아니므로 제외)
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }
        
        // 에라토스테네스의 체 : i가 소수라면, i의 배수들을 모두 소수가 아니라고 표시(false)
        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // M 이상 N 이하인 소수만 출력
        StringBuilder sb = new StringBuilder();
        for (int i = M; i <= N; i++) {
            if (isPrime[i]) {
                sb.append(i).append("\n");
            }
        }
        
        // 한꺼번에 결과 출력
        System.out.print(sb);
    }
}

알고리즘 해설

  1. 소수 판별 배열(isPrime)
    • boolean[] isPrime = new boolean[N + 1];
    • i번 인덱스를 “숫자 i가 소수인가(true/false)”를 저장하는 용도로 사용
    • 0과 1은 소수가 아니므로 제외, 2부터 true로 초기화합니다.
  2. 반복(for (int i = 2; i * i <= N; i++))
    • i가 소수(true)인 경우, i*i부터 N까지 i 간격으로 뛰며 배수를 지웁니다.
    • i*i 이전의 배수들은 이미 이전 단계에서 처리되었습니다.
  3. 출력
    • M부터 N까지 순회하며 isPrime[i]가 true이면 출력합니다.
    • 많이 쓰는 최적화 팁: StringBuilder를 활용하여 출력 성능을 향상시킵니다.

마무리

  • 단순 반복(브루트포스) 접근:
    • 작은 범위에는 충분히 빠르지만, 최대 1,000,000까지 가면 비효율적
    • 각 수마다 최대 N\sqrt{N} 반복이 커서 비효율적.
  • 에라토스테네스의 체:
    • O(Nlog⁡log⁡N)O(N \log \log N) 알고리즘으로, 1,000,000 범위도 2초 내에 가능.
    • "한 번에 대량의 소수를 구하는" 상황에 최적화된 방법.

이렇게 시간 초과를 경험한 뒤, 에라토스테네스의 체로 알고리즘을 변경해서 문제를 해결할 수 있습니다.
소수 문제는 거의 항상 에라토스테네스의 체를 먼저 떠올리면 좋을 것 같습니다.
범위가 큰 경우, 단순 반복으로는 시간 초과가 날 가능성이 매우 큽니다.