[백준] 1929번 : 소수 구하기 _ JAVA ( 주석 설명 )

-번

→ '에라토스테네스의 채'를 이용한 소수 판별

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


public class Main {
    static boolean[] prime; //소수 : false, 합성수 : true

    //전체 시간복잡도 : O(log(log(N))
    //전체 공간복잡도 : O(N)
    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());

        prime = new boolean[N+1]; //배열의 인덱스는 0부터 시작하므로, N 까지 소수 판별을 위해서는 +1을 해주어야 한다.

        solve(N); //소수 판별 함수 실행

        for(int i=M;i<=N;++i){ //범위(M~N) 내의 소수 출력
            if(!prime[i]){
                System.out.println(i);
            }
        }
    }

    //시간복잡도 : O(log(log(N))
    //공간복잡도 : O(N)
    private static void solve(int num) {

        prime[1] = true; //1은 소수가 아니다.

        //num 을 두 수의 곱으로 표현한 순서쌍은
        //sqrt(num)*sqrt(num)을 기준으로 대칭을 이루고 있으므로,
        //그 이후의 값은 계산할 필요가 없다.
        //1978, 2581, 11653번 문제 참고
        for(int i=2;i<=Math.sqrt(num);++i){
            for(int j=i*i;j<=num;j+=i){ //i*2는 i==2일 때 모두 true 처리가 되므로, 약간의 효율을 더하기 위해 i*i을 사용한다.
                prime[j] = true;
            }
        }
    }
}