[1929번] 소수 구하기 ( 에라토스테네스의 체 )

이 문제는 일반적인 소수구하기로 풀면 시간 초과가 발생한다. (나머지 연산을 사용)

✅ 에라토스테네스의 체

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

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

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

손으로 따라가보자.

✅ 코드

1은 소수가 아니므로 값에 0이 들어가야 한다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int arr[] = new int[m + 1];

		//초기화로 어차피 인덱스 0번은 0이 되어있음.

		for (int i = 2; i <= m; i++) {
			arr[i] = i;
		}

		//1은 소수가 아니므로 탐색 안함
		for (int i = 2; i <= Math.sqrt(m); i++) {
			//소수이면 탐색 중지
			if (arr[i] == 0) continue;

			for (int j = i + i; j <= m; j = j + i) {
            //범위가 j+i인 것에 주의!
				arr[j] = 0;
			}
		}

		for (int i = n; i <= m; i++) {
			if (arr[i] != 0) {
				System.out.println(arr[i]);
			}
		}

	}
}