문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //m~n 소수 구하기
        //에라토스테네스 체 방법으로 구하기
        int m = sc.nextInt();//최소값
        int n = sc.nextInt();//최대값
        //boolean 배열로 true는 소수가 아니고, false는 소수다.
        boolean check[] = new boolean[n+1];
        check[0] = true;// 0,1는 소수가 아니다.
        check[1] = true;

        for(int i=2; i<=Math.sqrt(n); i++){//2의 배수부터 시작
            for(int j=i*i; j<n+1; j+=i){//배수들을 ture로 하면서 비소수를 나타낸다.
                if(check[j] ==true) //중첩이 되면 바로 스킵
                    continue;
                check[j] = true;
            }
        }
        for(int i=m; i<=n; i++){ //소수들 나타내기
            if(check[i] == false){
                System.out.println(i); //소수 출력
            }
        }
    }
}

느낀점

이번 문제는 에라토스테네스 체 방법을 자세히 알지 못했다. 원래 풀던 방식으로 풀었다가 시간 초과 했다.
이 문제를 통해 이번에 이해하게 되었다.

참고

https://st-lab.tistory.com/81