99클럽 코테 스터디 1일차 TIL + sieve of Erathostenes

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

import java.util.*;

public class Main {
	static boolean[] isPrime;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int m = scanner.nextInt();
		int n = scanner.nextInt();

		boolean[] isPrime = new boolean[n + 1];
		setPrime(isPrime);
		for (int i = m; i <= n; i++) {
			if (isPrime[i]) {
				System.out.println(i);
			}
		}
		scanner.close();
	}

	static void setPrime(boolean[] isPrime) {
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;
		for (int i = 2; i * i <= isPrime.length; i++) {
			if (isPrime[i]) {
				for (int j = i * i; j < isPrime.length; j += i)
					isPrime[j] = false;
			}
		}
	}
}

에라토스테네스의 체(Sieve of Eratosthenes)
소수를 빠르게 찾는 알고리즘

🧠 핵심 아이디어

• 2부터 시작해서 배수를 지워나감

• 지워지지 않은 수는 소수

• 최대 범위의 제곱근까지만 검사하면 됨!