알고리듬 - 소수 구하기(에라토스테네스의 체)

코딩 테스트 문제를 푸는 중 소수를 구해야 하는 상황이 종종 있어서 소수를 구하는 방법을 정리하고자 한다.

 

에라토스테네스의 체

에라토스테네스의 체는 소수를 구하는 대표적인 방법이다.

해당 방법은 수학자 에라토스테네스가 발견한 것으로 동작 과정은 아래와 같다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

위 그림을 보면 쉽게 이해할 수 있는데 2부터 시작해 N까지 배수를 지워나가는 형식이다.

 

여기서 중요한 점은 배수를 지우는 작업을 2 ~ 10까지만 진행하고 11부터는 모두 소수 처리를 했다는 것인데,

그 이유는 √N = √120 < 11이기 때문이다.

 

11부터 계산하지 않는 이유는

11의 배수를 파악하기 위해선 11 * 2, 11 * 3, ..., 11 * 10까지 11에 2 ~ 10을 곱해야 하는데

이는 모두 2 ~ 10의 배수이기 때문이다.

 

구현

내용이 어렵지 않으므로 바로 구현해 보았다.

 

인스턴스 변수 & 생성자

최댓값 n을 받으면 배열을 초기화하고 메서드를 불러온다.

    int[] prime;
    Eratosthenes(int n) {

        prime = new int[n + 1];

        for(int i = 0; i <= n; i++)
            prime[i] = i;

        primeCheck();
        print();
    }

 

primeCheck() & print() 메서드

    void primeCheck() {
        for(int i = 2; i <= Math.sqrt(prime.length - 1); i++) {
            
            if(prime[i] != 0)
                for(int j = i + i; j <= prime.length - 1; j += i)
                    prime[j] = 0;
        }
    }
    
    void print() {
        System.out.print("소수: ");
        for(int i = 2; i < prime.length; i++)
            if(prime[i] != 0)
                System.out.print(prime[i] + " ");
    }

√n까지만 돌면서 만약 지우지 않은 값이면 해당 값의 배수를 지운다.

print()에선 0, 1을 제외해야 하므로 int i = 2부터 시작한다.

 

아래는 결과이다.

전체 코드

package practice;

public class IsPrime {
    public static void main(String[] args) {
        new Eratosthenes(200);
    }
}
class Eratosthenes {
    int[] prime;
    Eratosthenes(int n) {

        prime = new int[n + 1];

        for(int i = 0; i <= n; i++)
            prime[i] = i;

        primeCheck();
        print();
    }

    void primeCheck() {
        for(int i = 2; i <= Math.sqrt(prime.length - 1); i++) {
            
            if(prime[i] != 0)
                for(int j = i + i; j <= prime.length - 1; j += i)
                    prime[j] = 0;
        }
    }

    void print() {
        System.out.print("소수: ");
        for(int i = 2; i < prime.length; i++)
            if(prime[i] != 0)
                System.out.print(prime[i] + " ");
    }
}

 

아래는 에라토스테네스의 체를 이용할 수 있는 문제이다.

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

프로그래머스

 

에라토스테네스의 체는 일반적으로 시간복잡도 O(n log (log n))를 가진다.