[백준 자바] 1929번(소수 구하기) - 에라토스테네스의 체

난이도 - 실버 2

문제

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

입력

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

출력

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

 

---

 

728x90

에라토스테네스의 체를 사용한다. 2부터 n까지의 모든 수를 나열하고 2의 배수들을 모두 지운다. 남아있는 수 중에서 다음 수를 소수로 선택하고 그 수의 배수들을 모두 지운다. 이 과정을 범위의 끈까지 반복하고 남아있는 수들이 소수이다.

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

public class Main1929 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());

		boolean[] isPrime = sieveOfEratosthenes(N);

		StringBuffer sb = new StringBuffer();

		for (int i = M; i <= N; i++) {
			if (isPrime[i])
				sb.append(i).append('\n');
		}

		bw.write(sb.toString());

		bw.flush();
		br.close();
		bw.close();
	}

	static boolean[] sieveOfEratosthenes(int max) {
		boolean[] isPrime = new boolean[max + 1];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;

		for (int i = 2; i * i <= max; i++) {
			if (isPrime[i]) {
				for (int j = i * i; j <= max; j += i) {
					isPrime[j] = false;
				}
			}
		}

		return isPrime;
	}
}