[JAVA] 수학 연습문제 - 백준 1929

isChecked[]의 해당 인덱스(=실제 수)가 소수인지 검사 후, 소수가 아니면 true로 바꾼다.

 

입력이 최대 백만이므로, 배열의 사이즈는 백만+1 이다.

 

Boolean 배열의 기본값은 false이므로, 소수를 false로 저장한다.

소수인 수를 찾으면, 그 수의 배수들을 모두 true로 바꾼다.

 

이때, 정석대로라면 '소수*소수' 부터 반복문을 돌며 true로 바꿔야 하지만,

Integer의 범위를 넘어가는 경우가 생기므로, '소수*2' 부터 true로 바꿔준다.

 

저장된 배열에서 false인 인덱스를 출력하면, 소수를 출력하는 것과 같다.

 

import java.util.Scanner;
public class BOJ1929 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();

        boolean[] isChecked = new boolean[1000001];
        isChecked[1]=true;

        for(int i=2;i<=n;i++){
            if(isChecked[i]==false){
                for(int j=i*2;j<=n;j+=i){
                    isChecked[j]=true;
                }
            }
        }

        for(int i=m;i<=n;i++){
            if(!isChecked[i]){
                System.out.println(i);
            }
        }
    }
}