에라토스테네스의 체

✏️ 원리 이해하기

에라토스테네스의 체는 소수를 판별하는 간단한 알고리즘이다.

"소수가 되는 수의 배수를 지우고 남는 수는 모두 소수이다" 라는 원리이다.

 

정리하면,

1) 가장 작은 소수 2의 배수를 모두 지운다.

2) 다음 작은 소수인 3의 배수를 모두 지운다.

3) 지워지지 않는 수는 소수이다.

 

🚨 JAVA 로 구현해보기

만약, 120까지의 범위에서 소수를 구하는 문제일 때,

 

public class Solution {

	// 예제와 같이 120까지의 소수를 구하기 위해 120 선언.
	static boolean prime[] = new boolean[121];
    
    public static void main(String[] args) throws Exception{
		
        // 구하고자 하는 숫자 범위
        int N = 120;
        
        // 소수 -> false, 소수 아님 -> true
        // 0과 1은 소수가 아니므로 제외
        prime[0] = prime[1] = true;
        
        for(int i=2; i*i<=N; i++){
        	// prime[i]가 소수라면
            if(!prime[i]){
            	// prime[j] 소수가 아닌 표시
            	for(int j=i*i; j<=N; j+=i) {
                    prime[j] = true;   
                }
            }        
        }    
        
        // 소수 출력
        for(int i=1; i<=N;i++){
        	if(!prime[i]) System.out.print(i+" ");        
        }
        
    }
}

 

 

구하고자 하는 값의 제곱근까지만 배수제거를 실시하면 된다!