[알고리즘] 에라토스 테네스의 체란?

에라토스 테네스의 체란?

• 여러 개의 수가 소수인지 아닌지 판별할 때 사용하는 대표적인 알고리즘이다.
• 소수를 구하는 가장 기본적이고 이해하기 쉬운 방법 중 하나이다.

 

어떻게 동작하는가?

1. 리스트 생성: 2부터 원하는 최대 숫자 N까지의 리스트를 만듦
2. 첫 번째 소수 선택: 가장 작은 소수인 2부터 시작
3. 배수 제거: 선택한 소수의 배수를 리스트에서 제거하거나 표시
4. 다음 소수 찾기: 리스트에서 다음으로 남아있는 수를 선택하고, 이 수의 배수를 제거
5. 반복: 이 과정을 N의 제곱근까지 반복

에라토스 테네스의 체 동작과정

 

 

시간 복잡도는??

• 에라토스테네스의 체의 시간 복잡도는 놀랍게도 O(N log log N)이다.
• log log N은 매우 천천히 증가하는 함수로, N이 실용적인 범위 내에서는 거의 상수에 가깝다.
• 즉, 해당 알고리즘은 사실상 선형 시간에 가까운 성능을 보인다.

 

공간 복잡도는??

• N까지의 모든 수에 대한 정보를 저장해야 하므로, 공간복잡도는 O(N)이다.

 

장단점은??

• 위처럼 시간 복잡도가 매우 빨라 다수의 소수 찾는 문제에 적합하다.
• 하지만,  N 크기의 배열, 리스트가 필요로 하므로, 메모리 한정된 문제에서는 해당 알고리즘을 사용하기 어렵다.

 

[코드]

boolean[] arr = new boolean[N]; // N개의 크기를 가진 배열 초기화

for (int i = 0; i < arr.length; i++) // 모든 배열 요소를 true로 초기화
    arr[i] = true;

arr[0] = arr[1] = false; // 0과 1은 소수가 아니므로 false로 설정

for (int i = 2; i <= Math.sqrt(arr.length); i++) { // 2부터 √N까지 반복
    if (arr[i]) { // 만약 arr[i]가 true(소수)라면
        for (int j = i * i; j < arr.length; j += i) // i의 배수들을 순회
            arr[j] = false; // i의 배수는 소수가 아니므로 false로 설정
    }
}

 

왜 제곱근을 사용하는가??

제곱근을 사용하는 이유는 두 가지다.

효율성 향상

• 합성수 N은 최소 하나의 소인수를 갖는데, 그 소인수는 √N 이하이다.

이미 처리된 배수 제거

• N 이상의 수에 대한 배수는 이전에 처리된 작은 수들의 배수로 이미 체크되었기 때문에, 중복 검사를 피할 수 있다.

예시

N = 50일 때, √50 ≈ 7.07이므로, i는 2부터 7까지 검사하면 충분하다.
예를 들어, 49는 7×7로 이루어져 있으며, 7까지 검사하면 7의 배수인 49를 제외할 수 있다.

 

마무리하며..

• 에라토스 테네스의 체를 이용한 백준 문제 [1929 - 소수 구하기]를 풀며 글을 마치겠다.

 

[최종코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        boolean arr[] = new boolean[1000001];

        for (int i = 0; i < arr.length; i++)
            arr[i] = true;

        arr[0] = arr[1] = false;

        for (int i = 2; i < Math.sqrt(arr.length); i++) {

            if (arr[i]) {

                for (int j = i*i; j < arr.length; j += i)
                    arr[j] = false;
            }
        }

        for (int i = m; i <= n; i++) {

            if (arr[i] == true)
                System.out.println(i);
        }
    }
}