[백준] 1929 : 소수 구하기 JAVA 풀이

우선 구현을 해봤는데..계속 출력 초과나 오답이라고 나와서 결국 서치를 해봤다.

 

1. 소수인지 판별하고 싶은 범위만큼 배열을 만든다.(기본값 false)

2. 2부터 특정 수의 배수인 수들을 지운다.(자기자신은 지우지 않음)

3. 배열에서 false인 값들을 출력한다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main{
    public static boolean[] primeList; // 소수인지 판별하는 배열 생성. 기본값 false
    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()); 
        primeList = new boolean[N+1];
        get_prime();
        
        for(int i=M;i<=N;i++){
            // 소수라면 출력
            if(!primeList[i]) System.out.println(i);
        }
    }
    
    public static void get_prime(){
        primeList[0] = primeList[1] = true; // 0과 1은 소수가 아니니 true로 변경
        
        // 2부터 소수를 판별할 범위의 제곱근이하까지 반복
        for(int i=2;i<=Math.sqrt(primeList.length);i++){
            if(primeList[i]) continue; // 소수가 아니면 스킵
            for(int j=i*i;j<primeList.length;j+=i) primeList[j] = true;
            // 특정수의 배수인 수는 소수가 아니므로 true로 변경
        }
    }
}