소수 생성을 위한 에라토스테네스의 체는 얼마나 효율적인가요?

가장 우아한 소수 생성: 체 접근 방식

소수 생성 문제에 직면했을 때 코드의 우아함을 추구하는 것은 고귀한 추구입니다. 소수를 찾는 방법은 다양하지만 에라토스테네스의 체는 단순성과 효율성이 가장 뛰어납니다.

에라토스테네스의 체는 1부터 n까지의 숫자를 나타내는 n 길이의 부울 배열을 생성하여 작동합니다. 배열은 처음에 모든 요소에 대해 true로 설정되어 각 숫자가 잠재적인 소수임을 나타냅니다. 그런 다음 알고리즘은 표시되지 않은 첫 번째 숫자인 2부터 시작하여 배열을 반복합니다. 배열의 값을 false로 설정하여 2의 모든 배수를 소수가 아닌 것으로 표시합니다. 그런 다음 표시되지 않은 다음 숫자인 3으로 이동하고 프로세스를 반복하여 3의 모든 배수를 소수가 아닌 것으로 표시합니다. 이는 표시되지 않은 마지막 숫자 √(n)까지 계속됩니다.

이 접근 방식을 사용하면 에라토스테네스의 체는 소수를 찾는 데 필요한 확인 횟수를 크게 줄여 매우 효율적인 솔루션을 제공합니다. Sieve의 다음 Java 구현을 고려하십시오.

<code class="java">public static BitSet computePrimes(int limit) {
    BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j < limit; j += i) {
                primes.clear(j);
            }
        }
    }
    return primes;
}</code>

이 코드는 1부터 n까지의 숫자를 나타내는 BitSet을 생성하고 모든 요소를 ​​처음에 true로 설정합니다. 그런 다음 배열을 반복하여 각 소수(2로 시작)의 모든 배수를 소수가 아닌 것으로 표시합니다. 결과는 true로 설정된 유일한 요소가 소수를 나타내는 BitSet입니다.

위 내용은 소수 생성을 위한 에라토스테네스의 체는 얼마나 효율적인가요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!