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

문제

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

입력

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

출력

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

---

- 에라토스테네스의 체 원리

1) 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.

2) 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.

3) 배열의 끝까지 2번을 반복한 후 배열에서 남아 있는 모든 수를 출력한다.

public static void main(String[] args) {	// 에라토스테네스의 체
		
		Scanner sc = new Scanner(System.in);
		
		int n1 = sc.nextInt();	// 처음
		int n2 = sc.nextInt();	// 끝
		
		int arr[] = new int[n2 + 1];
		
		for (int i = 2; i <= n2; i++) {		// 2의 배수부터 시작
			arr[i] = i;
		}
		
		for (int i = 2; i <= Math.sqrt(n2); i++) {	// Math.sqrt(): 제곱근 구하기
			if (arr[i] == 0)
				continue;
			
			for (int j = i + i; j <= n2; j = j + i) {	
				// j = i + i: 몇 배수로 할 건지 정해줌, j = j + 1: 배수만큼 늘어나서 소수 판멸
				arr[j] = 0;
			}
		}
		
		for (int i = n1; i <= n2; i++) {
			if (arr[i] != 0)	// 각 인덱스의 값이 0이 아닌 애들만 출력
				System.out.println(arr[i]);
		}
		
		sc.close();
	}