에라토스테네스의 체

• 기본 약수의 성질 이용
  -> 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.
  ex) 16의 약수 : 1 2 4 8 16 에서 2 x 8과 8 x 2는 대칭을 이룬다.
  즉, 우리는 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)만 확인하면 된다.
• 에라토스테네스의 체 알고리즘
  : 다수의 자연수에 대하여 소수 여부를 활용할 때 사용하는 대표 알고리즘

✅ 정의

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용 가능

• 구체적인 동작 과정

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 제거한다. (i는 제거하지 않는다.)
4. 더이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

💻 코드

import java.util.*;

public class SieveOfEratosthenes
{
    public static int n = 1000; // 2부터 1000까지의 모든 수에 대하여 소수 판별
    public static boolean[] arr = new boolean[n + 1];

    public static void main(String[] args) {
        Arrays.fill(arr, true); // 처음엔 모든 수가 소수인 것으로 초기화 (0과 1 제외)
        // 에라토스테네스의 체 알고리즘 수행
        for (int i = 2; i <= Math.sqrt(n); i++) // 2부터 n의 제곱근까지의 모든 수를 확인
        { // i를 제외한 i의 모든 배수를 지우기
            int j = 2;
            while(i * j <= n)
            {
                arr[i * j] = false; // 해당 수는 추후 출력하지 않음
                j += 1;
            }
        }

        for (int i = 2; i <= n; i++)
        if (arr[i]) System.out.print(i + " ");
    }
}

📝 정리

에라토스테네스의 시간복잡도 : O(NloglogN)

-> 선형 시간에 가까울 정도로 빠르나 메모리가 많이 필요하다.
(각 자연수에 대한 소수 여부를 저장할 필요가 있으므로)