[JAVA] 백준 #1929

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));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        boolean[] isPrime = new boolean[m + 1];

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

        for (int i = 2; i <= m; i++) {
            isPrime[i] = true;
        }

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

        for (int i = n; i <= m; i++) {
            if (isPrime[i]) {
                sb.append(i + "\n");
            }
        }

        System.out.println(sb);
    }
}

에라토스테네스의 체

에라토스테네스의 체(Sieve of Eratosthenes)는 소수를 찾기 위한 고대 그리스의 알고리즘이다. 이 방법은 주어진 범위 내에서 소수를 효율적으로 찾는 데 사용된다. 알고리즘의 기본 원리는 다음과 같다:

1. 초기화: 2부터 원하는 최대 숫자 ( n )까지의 모든 자연수를 나열한다.

2. 소수 찾기: 2부터 시작하여, 그 수의 배수를 모두 지웁니다. 이때 2는 소수로 남겨두고, 2의 배수는 제외한다.

3. 다음 소수 확인: 다음 남은 수(여기서는 3)를 선택하고, 그 배수를 모두 지운다.

4. 반복: 이 과정을 ( \sqrt{n} )보다 작은 수까지 반복한다. 즉, ( p )가 ( \sqrt{n} )보다 작을 때까지 계속 진행한다.

5. 결과: 남은 수들은 모두 소수이다.

예를 들어, 30까지의 소수를 찾고자 할 경우, 이 방법을 사용하면 2, 3, 5, 7, 11, 13, 17, 19, 23, 29가 소수로 남게 된다.

에라토스테네스의 체는 간단하고 효율적이며, 특히 작은 소수를 찾는 데 유용하다. 시간 복잡도는 O(n log(logn))으로, 큰 범위의 소수를 찾는 데 적합하다.