[java] 자바를 활용한 에라토스테네스의 체 알고리즘

15 Dec 2023

java

에라토스테네스의 체( 에라토스테네스의 체 알고리즘)는 특정 범위 내의 모든 소수를 찾는 효율적인 알고리즘입니다. 이 알고리즘을 사용하여 주어진 범위 내의 모든 소수를 찾고 출력하는 간단한 자바 프로그램을 작성해 보겠습니다.

에라토스테네스의 체 알고리즘 구현

import java.util.ArrayList;
import java.util.List;

public class SieveOfEratosthenes {
    public static List<Integer> findPrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        return primes;
    }

    public static void main(String[] args) {
        int n = 30;
        List<Integer> primes = findPrimes(n);
        System.out.println("소수: " + primes);
    }
}

코드 설명

findPrimes 메서드는 입력 n을 받아 에라토스테네스의 체 알고리즘을 사용하여 2부터 n까지의 모든 소수를 찾아 List에 담아 반환합니다.
불리언 배열 isPrime을 사용하여 각 숫자의 소수 여부를 추적합니다.
두 번째 for 루프에서는 i의 배수를 소수에서 제외하기 위해 해당 요소를 false로 설정합니다.
main 메서드에서는 findPrimes를 호출하여 30 이하의 소수를 찾고 출력합니다.

이제 위의 코드를 실행하면 30 이하의 모든 소수가 출력됩니다.

에라토스테네스의 체 알고리즘을 사용하면 비교적 큰 범위 내의 소수를 효율적으로 찾을 수 있습니다.

에라토스테네스의 체 알고리즘 구현

코드 설명

참고 자료