에라토스테네스의 체 (JAVA)

📍 에라토스테네스의 체 란?

: 소수를 찾는 빠르고 효율적인 방법이다. 특정 범위 내에서 소수를 찾을 때 O(N log log N) 의 시간 복잡도로 동작하여 매우 빠르다.

1. 단일 숫자 소수 여부 확인

• 시간 복잡도 : O(√N)

어떤 수 N이 소수인지 판별하려면, 1과 자기 자신을 제외한 다른 약수가 존재하는지 확인해야 한다. 하지만, 굳이 1부터 N까지 모두 나눠볼 필요 없이, N의 제곱근(√N)까지만 검사하면 된다.

어떤 수 N이 A × B로 나뉜다고 하면, A와 B 중 적어도 하나는 √N 이하이다.
→ 즉, √N까지만 확인해도 나머지는 자동으로 체크된다.

예제
N = 36 이라 할 때
36을 약수 쌍으로 표현해보면:
(1,36),(2,18),(3,12),(4,9),(6,6),(9,4),(12,3),(18,2),(36,1)

√N = 6이다. (6,6)까지만 검사를 하면 대칭적이기 때문이다.

public static boolean isPrime(int n) {
	if (n < 2) return false; // 0과 1은 소수가 아님
	for (int i = 2; i * i <= n; i++) { // √N까지만 검사
		if (n % i == 0) return false; // 나누어 떨어지면 소수가 아님
    }
	return true;
}

2. 에라토스테네스의 체 원리

• O(N log log N)

에라토스테네스의 체는 소수만큼 배열을 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수를 모두 지운다.
배열을 생성하여 초기화한다. (지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)

예제
N = 30 이라면

- 초기 상태 (2~30):
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]

- 2는 소수 → 2의 배수 제거  
[2, 3, X, 5, X, 7, X, 9, X, 11, X, 13, X, 15, X, 17, X, 19, X, 21, X, 23, X, 25, X, 27, X, 29, X]  

- 3은 소수 → 3의 배수 제거  
[2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X, X, 17, X, 19, X, X, X, 23, X, 25, X, X, X, 29, X]  

- 5는 소수 → 5의 배수 제거  
[2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X, X, 17, X, 19, X, X, X, 23, X, X, X, X, X, X, 29, X]  

- 7은 소수 → 7의 배수 제거  
[2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X, X, 17, X, 19, X, X, X, 23, X, X, X, X, X, X, 29, X]  

import java.util.Arrays;
public static boolean[] sieve(int n) {
	boolean[] isPrime = new boolean[n + 1];
	Arrays.fill(isPrime, true); // 처음엔 모든 수를 소수로 가정
	isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

	for (int i = 2; i * i <= n; i++) {
		if (isPrime[i]) { // 소수라면
			for (int j = i * i; j <= n; j += i) { // i의 배수 지우기
				isPrime[j] = false;
            }
        }
	}
	return isPrime;
}

3. 프로그래머스 (JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/12921

import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] arr = sieve(n);
        for (int i=1; i<=n; i++) {
            if (arr[i]) answer++;
        }
        return answer;
    }
    private static boolean[] sieve(int n) {
	    boolean[] isPrime = new boolean[n + 1];
	    Arrays.fill(isPrime, true); 
	    isPrime[0] = isPrime[1] = false; 

	    for (int i = 2; i * i <= n; i++) {
		    if (isPrime[i]) { 
			    for (int j = i * i; j <= n; j += i) {
				    isPrime[j] = false;
                }
            }
	    }
	    return isPrime;
    }
}