에라토스테네스_체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법.

이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

따지고 보면 f(x)=x1P(x)f(x)=1P​(x)x​[1]의 수열을 표로 시각화한 것이라고 볼 수 있다.

 

1. solution(int n) - 에라토스테네스의 체

public int solution(int n) {
	int answer = 0; int[] ch = new int[n+1];
    
    for(int i=2; i<=n; i++) { // (1) 2부터 n까지 반복 
    	if(ch[i] == 0) { // (2) 아직 체크되지 않은 소수라면 
        	answer++; 
            for(int j=i; j<=n; j=j+i) { // (3) i의 배수를 체크 (에라토스테네스의 체) 
            	ch[j] = 1; 
            } 
   		} 
    } 
	return answer; 
}

 

최종 복잡도

O(nlog⁡log⁡n)
에라토스테네스의 체의 특성상 매우 효율적임.

2. solution2(int n) - 단순 소수 판별 구현

시간 복잡도 분석

1. 외부 for 루프: O(n)
   • 2부터 n까지 모든 수를 순회
2. 내부 for 루프: O(n)  
   • 각 수 iii에 대해 2부터 i−1까지 나눠보며 확인
   • 최악의 경우 O(n) (예: n이 소수일 경우, 내부 루프가 i−1번 수행됨)

최종 복잡도

O(n2)
모든 수 i에 대해 최대 i−1번 반복하는 구조이므로 매우 비효율적.

결론: 속도 비교

알고리즘시간 복잡도효율성

solution(n) (에라토스테네스의 체)	O(nloglogn)	✅ 매우 빠름
solution2(n) (단순 소수 판별)	O(n2)	❌ 매우 느림

• 에라토스테네스의 체(solution)는 수백만까지도 빠르게 계산 가능
• 단순 소수 판별(solution2)는 nnn이 10,000만 넘어가면 거의 사용 불가능

소수 찾기 관련 알고리즘 일때는 에라토스테네스의 체를 활용하는게 속도 적인 면에서 매우 빠르다!!