어떻게 효율적으로 소수를 생성할 수 있나요?

우아하고 효율적인 소수 생성

프로그래밍 영역에서 우아하고 효율적인 소수 생성 방법을 찾는 것은 고전적인 일입니다. 도전. 간결성과 성능 사이의 균형을 맞추는 접근 방식을 살펴보겠습니다.

n보다 작거나 같은 소수의 수를 pi(n) ≒ n / log(n)로 추정하는 소수 정리를 사용해 보세요. . 이 추정치는 소수를 식별하는 데 사용할 수 있는 체 크기의 상한을 제공합니다.

에라토스테네스의 체라고도 알려진 체 방법은 일련의 숫자를 반복하여 소수가 아닌 모든 숫자를 제거합니다. 합성으로 표시하여 소수로 표시합니다. 이 작업을 위해 BitSet을 활용하여 소수 집합을 나타낼 수 있습니다. 각 비트는 범위 내의 숫자에 해당합니다.

아래는 이 우아하고 효율적인 소수 생성 방법을 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초 만에 처음 백만 개의 소수를 효율적으로 생성합니다. 정밀도와 속도가 결합되어 다양한 컴퓨팅 시나리오에서 소수를 생성하는 데 유용한 도구입니다.

위 내용은 어떻게 효율적으로 소수를 생성할 수 있나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!