[백준] 1929번 - 소수 구하기

문제 >

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

 

입력 >

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

 

출력 >

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

 

해결방법 > 

입력 데이터가 최대 1,000,000이므로 아리토스테네스의 체를 사용.

에라토스테네스의 체는 소수를 구하는 방법으로 

2부터 시작해서 각 소수의 배수를 모두 제거해서 소수를 판별해야할 데이터를 줄이는 방식이다.

 

package baekjoon;

import java.util.*;

public class BOJ_1929{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int start = sc.nextInt();
		int end = sc.nextInt();
		int[] a = new int[end + 1];
		
		for(int i = 2; i < end + 1; i++) {
			if(a[i] == 1)
				continue;
			for(int j = 2; ;j++) {
				if(i * j > end)
					break;
				a[i * j] = 1;
			}
		}
		
		start = (start > 2) ? start : 2;
		
		for(int i = start; i <= end; i++) {
			if(a[i] == 0)
				System.out.println(i);
		}
		
	}
}

 

문제링크 >

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기