주어진 범위 내에서 소수를 효율적으로 찾는 방법은 무엇입니까?

주어진 범위에서 소수 찾기

수학에서 소수는 1과 자신을 제외한 다른 숫자로 나누어지지 않는 1보다 큰 정수입니다. 특정 범위 내에서 소수를 찾는 것은 일반적인 프로그래밍 작업일 수 있습니다. JavaScript에서 이 문제에 접근하는 방법에 대한 자세한 설명은 다음과 같습니다.

무차별 접근 방식

제공된 코드 조각은 무차별 접근 방식을 사용하여 0에서 100 사이의 소수를 찾으려고 합니다. 숫자가 2에서 12 사이의 숫자로 나누어지는지 확인하고 제수가 없으면 숫자를 반환합니다. 그러나 이 접근 방식에는 몇 가지 단점이 있습니다.

• 특히 더 큰 범위의 경우 비효율적입니다.
• 더 큰 범위의 경우 소수를 찾기 위해 확장하기가 어렵습니다.

에라토스테네스의 체

소수를 찾는 더 효율적인 알고리즘을 에라토스테네스의 체라고 합니다. 작동 방식은 다음과 같습니다.

1. 길이가 최대 1인 sieve라는 배열을 만듭니다.
2. 배열의 모든 요소를 ​​false로 초기화합니다(false는 숫자가 소수임을 의미함).
3. 2부터 최대값의 제곱근까지 sieve 배열을 반복합니다.
4. 각 소수 i에 대해 sieve[i j]를 설정하여 모든 배수를 소수가 아닌 것으로 표시합니다. i j에서 max까지 모든 j에 대해 true로 변환합니다.
5. 반복 후 시브 배열에서 표시되지 않은 숫자는 소수입니다.

JavaScript에서 코드는 에라토스테네스의 체는 다음과 같습니다.

<code class="js">function getPrimes(max) {
    var sieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!sieve[i]) {
            // i has not been marked -- it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                sieve[j] = true;
            }
        }
    }
    return primes;
}</code>

이 접근 방식은 O(n log log n)의 시간 복잡도를 가지며, 이는 무차별 접근 방식보다 훨씬 효율적입니다.

위 내용은 주어진 범위 내에서 소수를 효율적으로 찾는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!