📝문제

처음엔 무식하게 2중 for문으로 범위 안의 모든 수를 1부터 해당 수까지의 수로 나누는 방법을 택했다가 시간초과가 나왔다.
아! 역시 이 방법으로 풀릴리가 없구나를 체감하고 무슨 방법이 있을까 고민고민하던 중
내가 즐겨 보는 테크(?) 블로거인 Toram님의 포스팅에서 이것을 푸는 수학적인 방법이 있었다는 것이 떠올랐다.
검색했더니 역시 있었고, "에라토스테네스의 체"라고 불리는 정리를 배울 수 있었다.
위키피디아에 검색해서 풀이과정을 훓었고, 그 방법대로 로직을 짜서 풀었더니 통과할 수 있었다.

📌코드

package Baekjoon;

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

/**
 * 2중 for문을 사용해서 범위 안에 수를 직접 나누어보는 방법 : 시간초과
 * 해결방법 : 에라토스테네스의 체
 */

public class BOJ1929 {
    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());
        int[] num = new int[n+1];//소수가 아닌 것에 1
        num[1] = 1;//1은 소수가 아니다
        //에라토스테네스의 체
        for(int i = 2; i*i <= n; i++){
            if(num[i] == 0){
                for(int j = i*2; j <= n; j+=i){
                    num[j] = 1;
                }
            }
        }
        for(int i = m; i <= n; i++){
            if(num[i] == 0) System.out.println(i);
        }
    }
}