[백준] 자바 1929 소수 구하기

문제

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

입력

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

출력

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

---

테스트 케이스

 

입력 1

5 100

출력 1

5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

 

입력 2

3 16

출력 2

3
5
7
11
13

 

입력 3

1 4

출력 3

2

3

---

접근

정답률 27프로로 특정한 알고리즘을 알면 풀고 모르면 못 푸는 문제인 듯합니다...

해당 문제를 풀기 위해 알아야 할 알고리즘은 에라토스테네스의 체입니다.

 

말 그대로 체로 소수를 걸러내는 것입니다.

특정한 값까지의 소수를 구할 수 있는 알고리즘입니다.

간단하게 설명하자면 50까지의 소수를 알고 싶을 때,

2부터 50까지의 2의 배수를 모두 제거합니다.(자신인 2를 제외하고)

그리고

3부터 50까지의 3의 배수를 모두 제거합니다.(자신인 3을 제외하고)

그리고

4부터 50까지의 4의 배수를 모두 제거합니다.(자신인 4를 제외하고)

...

...

50부터 50까지의 50 배수를 모두 제거합니다.(자신인 50을 제외하고)

이렇게 하고 나서 제거되지 않은 수들이 소수입니다.

 

이 알고리즘을 이용하니 간단하게 문제가 해결되었습니다.

---

코드

import java.awt.desktop.SystemEventListener;
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	/*
 	 1929 problem
	*/
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		boolean arr[] = new boolean[end+1];
		arr[1] = true;
		
		for(int i=2; i<=end; i++) {
			for(int j=2; i*j<=end; j++){
				arr[i*j] = true;
			}
		}
		for(int i=start; i<=end; i++) {
			if( !arr[i]) {
				bw.write(String.valueOf(i)+"\n");
			}
		}
		bw.flush();
		br.close();
		bw.close();
	}
}

---

주의

1은 소수가 아닙니다.