[BAEKJOON] - 1929번 : 소수 구하기

1929번 문제 링크

⏲️ 시간 복잡도

• 소수를 구하는 문제는 에라토스테네스의 체를 사용하는 것이 가장 빠르고 확실한 방법이다.

📜 로직

• 에라토스테네스의 체를 활용하여 m부터 n까지의 수 중 소수를 판별해내는 문제이다.

1. 소수여부 판별을 위한 배열을 n + 1 만큼의 길이로 선언한다.
2. 2 ~ √n 만큼의 수를 반복하여 연산 수행.
3. 자기 자신이 아닌 수부터 n까지의 수 중 배수인 수를 걸러낸다.
4. m ~ n까지의 수를 출력한다.

😀 성공

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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringBuilder sb = new StringBuilder();
        
        String[] s = br.readLine().split(" ");
        
        br.close();
        
        int m = Integer.parseInt(s[0]);
        
        int n = Integer.parseInt(s[1]);
        
        boolean[] isPrime = new boolean[n + 1];
        
        Arrays.fill(isPrime, true);
        
        isPrime[0] = isPrime[1] = false;
        
        for(int i=2; i <= Math.sqrt(n); i++){
            if(!isPrime[i]) continue;
            
            for(int j = i*2; j <= n; j += i){
                isPrime[j] = false;
            }
        }
        
        for(int i=m; i <= n ; i++){
            if(isPrime[i]){
                sb.append(i).append("\n");
            }
        }
        
        System.out.println(sb);
    }
}