백준 / 1929 소수구하기 (수정필요)

문제

풀이

M이상 N이하의 소수를 모두 출력하는 문제이다.
다음의 문제를 풀기 위해서 쓰는 방법은 주로 '에라토스테네스의 체'이다.

'에라토스테네스의 체'에 대한 설명은 다음 링크의 설명을 참고하자
https://velog.io/@dogit/%EB%B0%B1%EC%A4%80-2581-%EC%86%8C%EC%88%98

코드

import java.util.*;

public class Main {
    public static void main(String args[]) {
    
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        //에라토스테네스의 체 알고리즘
        boolean[] check = new boolean[m+1];
        check[0] = check[1] = true;
        
        for (int i=2; i*i <= m; i++) {
            if (check[i] == true) {
                continue;
            }
            for (int j=i+i; j<=m; j+=i) {
                check[j] = true;
            }
        }
        
        for (int i=n; i<=m; i++) {
        	// false = 소수 
            if (check[i] == false) {
                System.out.println(i);
            }
        }
    }
}

출처 : https://www.acmicpc.net/problem/1929