[Algorithm] 에라토스테네스의체

에라토스테네스의 체

에라토스테네스의 체는 에라토스테네스가 고안했다고 여겨지는 소수 판정 방법으로, 자연수를 순서대로 늘어놓은 표에서 소수는 남겨두고 소수의 배수(합성수)를 지워나가면서
소수 목록을 얻는 것을 말한다. (소수의 개수)

소수를 판별하는 세가지 방법

소수는 영어로하면 Prime Number이다.
우리는 Java로 파라미터로 받은 정수가 소수인지 함수인지 판단하는 함수를 만들어 볼 것 이다.

1. 임의의 수 i를 사용하여 n-1 까지 반복하면서 증가하는 수로 n을 나눴을 때 나머지가 0인지 확인하는 방법 (간단한 방법)

    public boolean checkPrimeNumber(int n){
        boolean result = true;

        if( n < 2 ){
            result = false;
        }else if( n == 2 ){
            result = true;
        }else{
            for(int i = 3; i < n; i++){
                if(n % i == 0){
                    result = false;
                    break;
                }
            }
        }

        return result;
    }

1. 2 미만의 자연수에 소수는 없다.
2. 2는 소수이다.
3. 2 보다 큰 숫자들은 임의의 수 i를 사용하여 n-1 까지 반복하면서 i로 n을 나눴을때 나머지가 0인지 확인한다.

시간복잡도는 O(n)이다

2. 임의의 수 n의 제곱근 까지 반복하면서 2씩 증가하는 하는 수로 n을 나눴을 때 나머지가 0인지 확인하는 방법 (수학적으로 소수의 증명을 활용한 방법)

    public boolean checkPrimeNumber(int n){
        boolean result = true;

        if( n < 2 ){
            result = false;
        }else if( n == 2 ){
            result = true;
        }else{
            if( n % 2 != 0){
                for(int i = 3; i < Math.sqrt(n); i+=2){
                    if(n % i == 0){
                        result = false;
                        break;
                    }
                }
            } else {
                result = false;
            }
        }

        return result;
    }

1. 2 미만의 자연수에 소수는 없다.
2. 2는 소수이다.
3. 2 보다 큰 소수는 2로 나누면 항상 나머지가 있습니다.
4. 제곱근까지 범위를 지정하는 이유는 n이 소수이기 위해 필요 충분조건인 'n은 n의 제급근보다 작은 어떤 수로도 나눠지지 않는다.'
   ex) 9는 9의 제곱근인 3보다 크지 않은 숫자 2로 나눠지지 않는다.
   근데 만약 나눠진다면 그것은 소수가 아니다.
5. 2씩 증가하는 이유는 3번 내용을 한번더 하지 않기 위해서이다.

시간복잡도는 O(n^1/2) 이다.

3. 자연수를 순서대로 늘어놓은 표에서 소수는 남겨두고 소수의 배수(합성수)를 지워나가면서 소수 목록을 얻는다 (에라토스테네스의 체를 사용하는 방법)

    public boolean checkPrimeNumber(int n){
        boolean result = true;

        int number[] = new int[n+1];

        for(int i = 2; i <= n; i++){
            number[i] = i;
        }

        for(int i = 2; i <= Math.sqrt(n); i++){
            if(number[i] == 0){
                continue;
            }

            for(int j = 2*i; j <= n ; j += i){
                number[j] = 0;
            }
        }

        if(number[n] == 0){
            result = false;
        }

        return result;
    }

1. 에라토스테네스의 체는 소수의 개수를 구하는데 이 함수는 소수를 판별하는 함수이다. (판별을 위해 큰 배열의 사이즈를 사용하는 점은 효율적인 방법은 아닌 것 같다)
2. 자연수를 순서대로 늘어놓은 배열을 만들고 값을 입력한다.
3. 제곱근까지의 범위를 지정해서 2부터 시작해서 소수의 배수들을 0으로 바꿔준다.

하나의 수를 판별하는데 O(n+1)이라는 공간복잡도가 요구되는데 여러개의 수를 판별해야 할때는 효율이 좋을 것 같다.

참고사이트

https://ju-nam2.tistory.com/19
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