첫 번째 N 소수를 생성하는 가장 우아한 방법은 무엇입니까?

소수를 생성하는 우아한 방법

목표는 첫 번째 generatePrimes(n) 소수를 반환하는 함수 n를 작성하는 것입니다. 이 기능을 구현하는 방법에는 여러 가지가 있으며 각 방법에는 장단점이 있습니다. 이 기사에서는 가장 우아한 방법을 살펴봅니다.

원래 접근 방식은 일반적으로 소수를 확인하기 위해 중첩 루프를 사용합니다. 이 접근 방식은 효과가 있지만 반복적이고 중첩된 구조로 인해 우아함이 부족합니다. 보다 우아한 접근 방식은 O(n log log n)의 시간 복잡도를 갖는 에라토스테네스의 체를 사용하는 것입니다.

에라토스테네스의 체는 처음에 모든 요소가 true로 설정된 n 크기의 부울 배열을 생성하여 작동합니다. 배열 인덱스는 0부터 n-1까지의 숫자를 나타냅니다. 알고리즘은 먼저 인덱스 0과 1의 요소를 소수가 아니기 때문에 false로 설정합니다. 그런 다음 각 인덱스 i에 대해 배열에 있는 i의 모든 배수를 false로 설정합니다. 이 과정은 n의 제곱근까지의 모든 인덱스에 대해 반복됩니다. 배열의 나머지 true 요소는 소수를 나타냅니다.

다음은 에라토스테네스의 체의 우아한 Java 구현입니다.

public static List<Integer> generatePrimes(int n) {
    if (n <= 0) {
        return new ArrayList<>();
    }
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }
    return primes;
}

이 코드는 에라토스테네스의 체를 사용하여 첫 번째 n 소수를 효율적이고 우아하게 생성합니다. 시간 복잡도는 O(n log log n)이고, 코드가 간결하고 명확하여 소수 생성에 이상적입니다.

위 내용은 첫 번째 N 소수를 생성하는 가장 우아한 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!