에라토스테네스의 체 - seive of eratosthenes

📗 에라토스테네스의 체 알고리즘

그리스의 수학자 에라토스테네스가 만들어 낸 소수를 구하는 방법으로 

프로그래밍 알고리즘에서 소수를 구할 때도 적용하여 사용한다.

 

✔️ 에라토스테네스의 체 알고리즘의 원리

에라토스테네스의 체 알고리즘의 원리는 

"소수의 배수인 수들을 전부 제외하면 소수만 남는다" 이다.

다시 말하면 소수의 배수들은 전부 소수가 아니기 때문에 

소수의 배수들만 전부 제외하면 소수만을 구할 수 있는 것이다.

 

 

 

🚨CODE

// 에라토스테네스의 체
boolean[] prime = new boolean[n];
public static void SeiveOfEratosthenes(){
    // true = 소수x , false = 소수
    prime[0] = prime[1] = true;

    for(int i = 2; i<=Math.sqrt(prime.length); i++){
        // 소수가 아니면 넘어간다
        if(prime[i])
            continue;
        // 소수이면
        for(int j = i*i; j<prime.length; j+=i){
            prime[j] = true;
        }
    }
}

 

 

✔️ 시간 복잡도

 O(N * log(log N))