에라토스테네스의 체

✅ "가장 작은 수 i" : 지워지지 않아 소수로 남아있는 값 중 가장 작은 값
✅ "i는 제거하지 않는다" : i는 그 자체로 소수이기 때문

동작 원리

✅ 26의 제곱근은 5.XX이다. 따라서 약수의 성질에 따라 5까지만 확인하면 된다.

소스

import java.util.*;

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

    public static void main(String[] args) {
        Arrays.fill(arr, true); // 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
        // 에라토스테네스의 체 알고리즘 수행
        // 2부터 n의 제곱근까지의 모든 수를 확인하며
        for (int i = 2; i <= Math.sqrt(n); i++) {
            // i가 소수인 경우(남은 수인 경우)
            if (arr[i] == true) {
                // i를 제외한 i의 모든 배수를 지우기
                // j는 배수 값
                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 + " ");
        }
    }
}

성능 분석

✅ 밑이 2인 log로 가정했을때, N이 백만이면 백만*4.XX