[백준 JAVA] 1929 소수 구하기

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

public class Main_1929에라토스테네스 {

    //문제
    //M이상 N 이하의 소수를 모두 출력하는 프로그램을 작성하시오

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

        // 소수를 구할 범위 입력 받기
        String[] input = br.readLine().split(" ");
        int m = Integer.parseInt(input[0]); // M 이상
        int n = Integer.parseInt(input[1]); // N 이하

        // 입력 범위 체크
        if (m < 1 || n > 1_000_000 || m > n) {
            return;
        }

        // M 이상 N 이하의 소수를 담을 배열 생성
        ArrayList<Integer> primes = countPrimes(m, n);

        // 출력
        for (int prime : primes) {
            System.out.println(prime);
        }
    }

    // 에라토스테네스의 체 알고리즘을 사용하여 M 이상 N 이하의 소수를 찾는 메서드
    private static ArrayList<Integer> countPrimes(int m, int n) {
        boolean[] isPrime = new boolean[n + 1]; // 0부터 n까지의 소수 여부를 저장할 배열
        ArrayList<Integer> primes = new ArrayList<>(); // 소수를 저장할 리스트

        //리스트에 저장된 각 소수를 하나씩 출력
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        // 에라토스테네스의 체 알고리즘 적용
        // 2부터 p의 개수를 n까지 반복한다
        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                //p의 배수들을 isPrime에 담아 false로 표시한다
                //i = p * p에서 시작하여, i를 p씩 증가시킴
                for (int i = p * p; i <= n; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        // m 이상 n 이하의 소수를 리스트에 추가
        //int i 는 무조건 2 < m < i 이다
        for (int i = Math.max(2, m); i <= n; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }

        return primes;
    }
}

 

소수면 역시 에라토스테네스의 체를 사용하라는 뜻.

 

시간복잡도

O(n log log n)

 

1. n까지의 모든 수에 반복하며 소수를 판별한다.

2. 각 소수 p에 대해 배수를 제외하는 과정에서 시간 복잡도는 O(n/p)이다.

3. 모든 소수에 대해 이 과정을 반복하기 때문에, n까지의 모든 수에 대해 소수를 판별하는 시간 복잡도는

log(log n) 으로 O(n log log n)이다.