[백준] 1929번 소수 구하기

해결

• M,N의 입력값은 1000000이하의 자연수이다. 대량의 소수를 구할때는 알고리즘 ‘에라토스테네스의 체’를 이용하면 효율적으로 구할 수 있다.

  [참고]
  https://velog.io/@dayoung_sarah/알고리즘-에라토스테네의-체

코드

public class Main {
    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());

		// 소수 여부 배열
        boolean[] primeArray = getPrimeArray(N);
        StringBuilder sb = new StringBuilder();
        for(int i=M; i<=N; i++) {
            if( !primeArray[i] ) {
                sb.append(i + "\n");
            }
        }
        System.out.println(sb);
    }
    
    // 특정 범위 내 소수 여부 배열 구하기
    public static boolean[] getPrimeArray(int max) {
        boolean[] primeArray = new boolean[max+1];
        primeArray[0] = true;
        primeArray[1] = true;
        
        for(int i=2; i<=Math.sqrt(max); i++) {
            if( primeArray[i] ) continue;
            
            for(int j=i*i; j<=primeArray.length; j += i) {
                primeArray[j] = true;
            }
        }
        
        return primeArray;
    }
}