**소수가 아닌 수(합성수)는 어떤 소수 p의 배수.**
그 **배수**를 한 번에 **모두 제거**하는 방식

🎯 문제 유형

• 구간(M ~ N) 안의 모든 소수 출력

🚮 선입견을 버리자

• 소수 풀이 문제 → √N 까지 나눠보면 되는 거 아닌가? → ❌
  • N이 1,000,000을 넘어가면 시간 초가 위험 존재
  • 따라서, N의 크기에 따라 더 좋은 방법을 생각해내야 하는 경우가 존재
• 에라토스테네스 체 방식의 시간복잡도는 O(N * log(log N))
  • 웬만한 모든 경우에서 통과할 수 있음

💭 어떻게 떠올릴까

• 구간에서 소수를 여러 개 출력, 혹은 여러 번 판정해야 할 경우 (리스트 생성)
• 범위 길이가 크면 클 수록 √ 판정 반복운 위험

✏️ 시간 복잡도

• 시간복잡도: O(N × log(logN))

📒 에라토스테네스의 체 풀이 방법

• 코드 예시

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(token.nextToken());
		int n = Integer.parseInt(token.nextToken());
		
		// comp[x] == true -> x는 합성수 (소수 X)
		// comp[x] == false -> 소수 후보 (최종적으로 소수 가능성 존재)
		boolean[] comp = new boolean[n + 1];
		
		// 0, 1은 합성수 처리
		comp[0] = true;
		comp[1] = true;
		
		// i는 소수 후보
		// i*i <= n 까지만 반복
		// ex) i=10이면, 2*5나 5*2나 똑같음 -> sqrt 기준으로, 사실상 동일한 연산 반복
		for (int i = 2; (long) i * i <= n; i++) {
			
			// 이미 합성수 처리 됐으면(4, 6, 8...), 소수가 아니므로 스킵
			if (comp[i]) {
				continue;
			}
			
			// i 가 소수면, i의 배수들은 전부 합성수
			// i*2, i*3 ... i*(i-1)은 이미 이전에 처리
			// 따라서 시작점을 i*i 로 설정
			// ex) i=5 면, 10(5*2)는 2에서, 15(5*3)는 3에서 이미 처리
			for (int j = i * i; j <= n; j += i) {
				comp[j] = true;  // 배수 제거 (합성수 처리)
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = Math.max(m, 2); i <= n; i++) {
			if (!comp[i]) {
				sb.append(i).append("\n");
			}
		}
		
		System.out.print(sb);
	}
}