[백준 온라인저지]소수구하기 - 수학

소수하기

이번 포스팅 문제는 1929번 문제입니다.

문제요약

에라토스테네스의 체 알고리즘을 이용하여 자연수 M이상 N이하의 소수를 출력하는 문제입니다.

풀이전략

에라토스테네스의 체 참고

구현하기

package BackJoon.수학;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/1929
 * 에라토스테네스의 체
 * @author troh
 */
public class _1929_소수구하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();
        
        boolean[] check = new boolean[num2+1];
        for(int i=2; i<=num2; i++) {
            if(!check[i]) {
                for(int j=i+i; j<=num2; j=j+i) {
                    check[j] = true;
                }
            }
        }
        
        int count = 0;
        for(int i=num1; i<=num2; i++) {
            if(i == 1) continue;
            
            if(!check[i]) {
                System.out.println(i);
            }
        }
    }
}
 

배운점

에라토스테네스의 체