Sieve of Eratosthenes

고대 수학자 에라토스테네즈가 만들어낸 소수를 찾는 방법. 마치 체를 사용하여 수를 걸러내는 듯한 방법으로 ‘에라토스테네즈의 체’ 라고 불린다. $f(x) = \frac{x}{1p(x)}$ 의 수열을 표로 시각화 한 것으로 볼 수 있다.

과정

예를 들어 1 ~ 100까지의 수들 중에서 소수를 찾는다고 가정하자.

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

일단 소수와 합성수도 아닌 1과 2를 제외한 2의 배수를 제거한다.

   2   3       5       7       9     
11   13   15   17   19  
21   23   25   27   29  
31   33   35   37   39  
41   43   45   47   49  
51   53   55   57   59  
61   63   65   67   69  
71   73   75   77   79  
81   83   85   87   89  
91   93   95   97   99  

그다음 3의 배수를 제거하고 4의배수로 제거하고 계속 나아간다. 하지만 4의 배수는 2의 배수를 제거할때 지워 졌기 때문에 지우지 않는다. 이후 5의 배수를 제거하고 마지막으로 7을 제외한 7의 배수도 제거한다.

   2   3       5        7       9     
11   13       17   19  
    23           29  
31           37      
41   43       47      
    53           59  
61           67      
71   73           79  
    83           89  
            97      

11이상의 소수들의 배수부터는 11 > $\sqrt{100}$ 이기 때문에 지울필요 없다. 즉 n 이하의 소수를 모두 찾고 싶다면 전부 나열한 이후에 2의배수, 3의배수, 4의배수.. 로 쭉 나누는 것이다. 아직까지는 소수들 간의 연관성이 밝혀 지지 않아 가장 빠른 방법이다.

구현

1 ~ N 까지의 수들 중에서 소수를 찾아내고 싶다면 N 전의 모든 배수를 찾아 볼 필요가 없다. N보다 작은수 M이 M=ab라면 a, b는 둘중 하나는 $\sqrt{N}$ 이하이다 즉 N보다 작은수 M은 $\sqrt{N}$ 보다 작은 수의 배수로만 체크 해도 전부 지워진다는 뜻이다.

import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

class Main{
    public static void main(String[] args) throws IOException{
        Scanner scanner = new Scanner(System.in);

        // 사용자로부터 N 값을 입력 받음
        System.out.print("소수를 찾을 범위의 상한 N을 입력하세요: ");
        int N = scanner.nextInt();

        // 입력받은 N 값이 1 이하인 경우 처리
        if (N < 2) {
            System.out.println("2 이상의 값을 입력해야 합니다.");
            return;
        }

        System.out.println("1부터 " + N + "까지의 소수:");

        // 1부터 N까지의 수를 하나씩 확인하여 소수인지 판별
        for (int num = 2; num <= N; num++) {
            boolean isPrime = true;

            // num이 소수인지 판별
            for (int i = 2; i <= Math.sqrt(num); i++) {
                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }

            // 소수인 경우 출력
            if (isPrime) {
                System.out.print(num + " ");
            }
        }

        scanner.close();
    }

}