백준 1929번 - 소수 구하기(Java)

백준 1929번 - 소수 구하기(Java)

 

문제

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

입력

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

출력

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

풀이 과정

1. 기존에 풀던 방식대로 하나 하나 소수 판별하는 방식을 사용했더니 시간 초과가 떴다.

2. boolean 배열을 만들고, 각 숫자들의 배수를 제외시켜나가 남은 숫자들이 소수가 되는 알고리즘을 사용했다.

 

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		int M = scanner.nextInt();
		int N = scanner.nextInt();
		int i,j = M;
		boolean list[] = new boolean[N + 1];
		Arrays.fill(list,true);
		
		list[1] = false;
		
		for (i = 2; i <= N; i++)
			for (j = 2; i*j <= N; j++)
				list[i * j] = false;

		for (i = M; i <= N; i++) {
			if(list[i]==true) {
				System.out.println(i);}
			}		
	}
}