문제

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

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

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

접근

소수 판정 문제의 대표적인 해결 방법은 에라토스테네스의 체 알고리즘을 사용하는 것이다. 2부터 판별할 소수 n사이의 모든 값 중 앞선 수의 배수를 모두 지워버리면 남은 수는 모두 소수라는 뜻이다.

n부터 m까지의 수 이므로, 2부터 m의 제곱근 까지의 수들의 배수를 모두 지워버리면 남아있는 수는 모두 소수다.

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		boolean [] prime = new boolean[m+1];
		for(int i = 0; i <= m; i++)
			prime[i] = true;
		prime[0] = false;
		prime[1] = false;
		
		for(int i = 2; i*i <= m; i++) {
			for(int j = i*i; j <= m; j+=i) {
				prime[j] = false;
			}
		}
		
		for(int i = n; i <= m; i++) {
			if(prime[i])
				System.out.println(i);
		}
	}
}