에라토네스의 체

목차

1.에라토네스의 체?

2.작동원리

3.예제

 

1.에라토네스의 체?

에라토네스의 체는 대 그리스의 수학자 에라토스테네스가 고안한 소수 판별 알고리즘이다. 이 알고리즘은 2부터 N까지의 자연수 중에서 소수를 효율적으로 찾는 방법으로, 현재까지도 널리 사용되고 있다.

2.작동원리

에라토스테네스의 체는 배수 제거 방식을 사용하여 소수를 판별한다. 초기에는 2부터 N까지의 모든 정수를 소수라고 가정한 뒤, 각 수의 배수를 지워나가면서 최종적으로 소수만을 남기는 방식입니다.

 

작동원리는 다음과 같습니다.

 

 만약에 n 이 30일 때

1. 2부터 30까지 나열
   → [2, 3, 4, 5, ..., 30]
2. 가장 작은 수인 2는 소수니까 남기고, 2의 배수들 제거
3. 남은 수 중 다음 작은 수(3)는 소수니까 남기고, 3의 배수들 제거
4. 남은 수 중 다음 작은 수(5)... 이런 식으로 진행
5. √n까지 반복, 이후 남은 수는 전부 소수!

3.예제

에라토네스의 체를 코드를 작성을 해보면 다음과 같습니다.

        int n = 30; // 원하는 범위의 숫자
        boolean[] isPrime = new boolean[n + 1];

        // 초기값: 모두 소수(true)로 설정
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;

        // 에라토스테네스의 체
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false; // i의 배수는 소수 아님
                }
            }
        }

        // 결과 출력
        System.out.println(n + " 이하의 소수:");
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
    }