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

문제

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

입력

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

출력

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

---

앞의 문제들처럼 풀었다가 시간 초과가 났다. 에라토스테네스의 체를 사용하는 문제였다.

에라토스테네스의 체는 소수를 구하는 알고리즘으로, 2부터 자기 자신을 제외한 자신의 배수들을 하나씩 지워나가는 알고리즘이다.

이때 끝까지 남아있는 수들이 소수에 해당한다.

그래서 먼저 배열을 선언하여 각 값을 초기화하였다. 이때 index를 그 값으로 사용하기 위해 N+1 크기의 배열을 선언하였다.

그리고 배열을 돌며 값이 0인 경우에는 continue로 지나가고, 0이 아닐 때에만 그 값의 배수를 지워주는 과정을 반복하였다.

이때 M이상 N이하의 범위지만 소수를 구할 때에는 2의 배수부터 지워줘야 하기 때문에 2부터 루프를 돌아야 한다.

package boj0728;

import java.util.Scanner;

public class BOJ_1929_소수구하기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();
		int[] arr = new int[N + 1];
		for (int i = 2; i <= N; i++)
			arr[i] = i;

		for (int i = 2; i <= N; i++) {
			if (arr[i] == 0) // 이미 지워진거면 pass
				continue;

			for (int j = i * 2; j <= N; j += i)
				// i의 배수를 찾아서 지움, 이때 i는 제외
				arr[j] = 0;

		}

		for (int i = M; i <= N; i++) {
			if (arr[i] != 0)
				System.out.println(arr[i]);

		}

	}
}