[알고리즘] 에라토스테네스의 체(Sieve of Eratosthenes)

에라토스테네스의 체 (Sieve of Eratosthenes)

① 에라토스테네스의 체 (Sieve of Eratosthenes)이란?

▷ 소수 판별 알고리즘입니다.

▷ 소수를 대량으로 빠르고 정확하게 구하는 방법입니다.

▷ 소수 : 양의 약수를 두 개만 가지는 자연수입니다.

public static boolean isPrimeNumber(int x) {
    int end = (int) Math.sqrt(x);
    for(int i = 2; i <= end; i++) {
        if(x % i == 0) return false;
    }
    return true;
}

   ▶ 소수를 판별할 때 O(N^(1/2)) 로 해결하는 방법입니다.

   ▶ 예를 들어 8의 경우 2 * 4 = 4 * 2와 같은 식을 대칭을 이루기 때문에 숫자의 제곱근까지만 약수의 여부를 검증하면 된다.

② 그림으로 보는 에라토스테네스의 체 (Sieve of Eratosthenes)

에라토스테네스의 체는 다음과 같은 절차로 진행됩니다.

1. STEP(1) : 원하는 숫자까지의 값을 초기화해줍니다.

2. STEP(2) : 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지웁니다. (즉, 자기 자신을 제외한 배수를 지워주면 됩니다.)

3. STEP(3) : 이미 지워진 숫자의 경우 건너뛰고 진행합니다.

 ▷ 위 그림 처럼 크기 25인 배열에 특정 값으로 배열을 초기화 합니다.

 ▷ 먼저 2의 배수를 지웁니다. (자기 자신은 제외합니다.)

▷ 3의 배수를 지웁니다. (자기 자신은 제외합니다.)

▷ 4는 이미 지워져있으므로 지우지 않고 건너 뜁니다.

▷ 5의 배수를 지웁니다. (자기 자신은 제외합니다.)

③ 에라토스테네스의 체 (Sieve of Eratosthenes) 코드

▷ isPrime 배열에는 소수인지 아닌지의 여부가 true/false 값으로 나와있습니다.

▷ isPrime[i]의 값이 true 값일 때는 primeList에 담아 줍니다.

▷ 16 line : j = i *2를 한 이유는 해당 숫자의 다음 배수부터 따져주기 위함입니다.

④ 에라토스테네스의 체 (Sieve of Eratosthenes) 관련 알고리즘 문제

(백준 2960) 에라토스테네스의 체 (https://www.acmicpc.net/problem/2960) 해결 코드

(백준 4948) 베르트랑 공준 (https://www.acmicpc.net/problem/4948) 해결 코드

(백준 1978) 소수 찾기 (https://www.acmicpc.net/problem/1978) 해결 코드

(백준 6588) 골드바흐의 추측 (https://www.acmicpc.net/problem/6588) 해결 코드

(백준 4973) 셀프 넘버 (https://www.acmicpc.net/problem/4973) 해결 코드

참고

1. https://kks227.blog.me/220785731077
2. https://blog.naver.com/ndb796/221233595886 (나동빈 님 블로그)