[백준 2960] 에라토스테네스의 체 (자바)

백준 2960번: 에라토스테네스의 체

문제 설명

에라토스테네스의 체 알고리즘을 사용하여 1부터 N까지의 숫자 중 소수를 찾고, S번째로 지워지는 수를 출력하는 문제입니다.

공식

package re_02;

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

public class BOJ_2960_에라토스테네스의체_공식 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // N개 이하에서 소수 및 소수갯수 구하기
        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);

        isPrime[0] = false;
        isPrime[1] = false;

        // 2부터  ~ i*i <= n
        // 각각의 배수들을 지워간다.
        for (int i = 2; i <= Math.sqrt(N); i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false;
                }
                //i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다.
            }
        }
        for (int i = 0; i < isPrime.length; i++) {
            if (isPrime[i]) {
                System.out.println(i);
            }
        }
    }
}

문제 접근 방법

1. 2부터 N까지의 숫자를 대상으로 에라토스테네스의 체 알고리즘을 사용하여 소수를 찾아냅니다.
2. 각 숫자의 배수를 지워 나가면서 지워진 숫자의 순서를 기록합니다.
3. S번째로 지워진 숫자를 출력합니다.

시간 복잡도 분석

O(N log log N)

에라토스테네스의 체 알고리즘은 일반적으로 O(N log log N)의 시간 복잡도를 가집니다. 이는 각 소수의 배수를 제거하는 과정이 효율적으로 이루어지기 때문입니다.

해결 방법

아래는 주어진 범위 내에서 소수를 찾아 S번째로 지워진 숫자를 출력하는 Java 코드입니다:

package re_02;

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

public class BOJ_2960_에라토스테네스의체 {
    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 S = Integer.parseInt(st.nextToken());

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

        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i; j <= N; j += i) {
                    if (isPrime[j]) {
                        isPrime[j] = false;
                        S--;
                        if (S == 0) {
                            System.out.println(j);
                            return;
                        }
                    }
                }
            }
        }
    }
}