[백준/java] 1929 소수 구하기 - 에라스토테네스의 체 사용

에라스토테네스의 체

www.acmicpc.net/problem/1929

1929번: 소수 구하기

문제

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

입력

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

출력

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

 

예제 입력	예제 출력
3 16	3 5 7 11 13

 

※ 문제 풀이 방식

(1) 에라스토테네스의 체 방식을 적용하여 푼다.

ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

package backjun;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class GetPrimeNumber {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int m = input.nextInt(), n = input.nextInt();

		List<Boolean> list = new ArrayList<Boolean>();
		list.add(false); list.add(false);
		for (int i = 2; i <= n; i++) list.add(true);

		for (int i = 2; i*i <= n; i++) {
			if(list.get(i)) {
				for (int j = i*i; j <= n; j += i) {
					list.set(j, false);
				}
			}
		}

		for (int i = m; i <= n; i++) {
			if(list.get(i)) System.out.println(i);
		}
	}
}