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

자연수 n이 주어졌을 떄 n까지의 자연수에 존재하는 모든 소수를 판별하는 알고리즘

체는 sieve, 즉 조리용 도구로 쓰이는 체를 말하는 거임, 처음에 체가 수학 용어인줄 알고 검색해봤음. 소수가 걸러지는 체라고 생각하면 개념 이해할 때 도움이 될거임

알고리즘 비교

custom 소수 판별 알고리즘

static boolean isPrime(int n) {
        if(n <= 1) return false;
        if(n <= 3) return true;
        for(int i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }

n을 넘지 않는 n의 제곱근까지의 수 중 n이 나눠질 수 있는 지 검사

eratosthenes 판별 알고리즘

static void eratosthenes(int n, boolean[] primeList) {
        for(int i = 2; i * i <= n; i++) {
            if(primeList[i]) {
                for(int j = i * i; j <= n; j += i) {
                    primeList[j] = false;
                }
            }
        }
    }

성능 비교 소스 코드

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

public class TimeTest {
    public static void main(String[] args) throws IOException {
        int targetNumber = 100 ;

        boolean[] primeList1 = new boolean[targetNumber + 1];

        boolean[] primeList2 = new boolean[targetNumber + 1];
        Arrays.fill(primeList2, true);
        primeList2[0] = false;
        primeList2[1] = false;

        // custom 소수 판별 알고리즘
        long startTime1 = System.nanoTime();

        for(int i = 0; i <= targetNumber; i++) {
            primeList1[i] = isPrime(i);
        }

        long endTime1 = System.nanoTime();

        double duration1 = (endTime1 - startTime1) / 1_000_000.0;

        // Eratosthenes의 체 알고리즘
        long startTime2 = System.nanoTime();

        eratosthenes(targetNumber, primeList2);

        long endTime2 = System.nanoTime();

        double duration2 = (endTime2 - startTime2) / 1_000_000.0;

        // 결과 출력
        System.out.println("Execution time: " + duration1 + " milliseconds");
        System.out.println("Execution time: " + duration2 + " milliseconds");
    }

    static boolean isPrime(int n) {
        if(n <= 1) return false;
        if(n <= 3) return true;
        for(int i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }

    static void eratosthenes(int n, boolean[] primeList) {
        for(int i = 2; i * i <= n; i++) {
            if(primeList[i]) {
                for(int j = i * i; j <= n; j += i) {
                    primeList[j] = false;
                }
            }
        }
    }
}

시간 측정 결과

효율적인 계산을 위한 핵심 포인트

n까지의 모든 자연수를 검사하는 것이 아니라 n의 제곱근까지만 검사

• 자연수의 제곱근을 기준으로 약수의 짝은 좌우 반전 형태의 대칭을 이룬다.
• 약수의 짝이 갖는 대칭적인 특징 때문에 구하고자 하는 자연수 n의 제곱근까지로 범위를 한정하여 소수를 판별해도 문제가 없다.(해당 범위 내에서 약수가 발견되지 않았다면 이후에도 없는 것임으로)

소수의 배수를 검사할 때 i * i부터 검사

• 소수인지 판별하려는 수를 i라 하고 i가 소수일 때 i의 배수를 j라 했을 때, 위에서 설명한 약수의 대칭적인 특징 때문에 i * i부터 배수 검사를 진행해도 문제가 없다.
• i는 1씩 증가하기 때문에 이미 i * (2 ~ i)까지의 수는 판별이 끝난 상태이다.