제한된 범위 내에서 소수를 어떻게 효율적으로 매핑할 수 있습니까?

제한된 범위에서 효율적인 소수 매핑

컴퓨터 과학 영역에서는 특정 범위 내의 소수를 식별하는 것이 일반적인 작업입니다. . 목표는 숫자를 "소수" 상태에 효율적으로 매핑하는 데이터 구조를 만드는 것입니다.

한 가지 접근 방식은 부울 함수 isprime(n)을 사용하는 것입니다. 그러나 최적의 메모리 소비를 위해서는 사용자 정의 데이터 구조가 바람직합니다. N이 상수인 범위(1, N]의 경우 다음 고려 사항이 필수적입니다.

에라토스테네스의 체 변형

고전적인 에라토스테네스의 체는 다음과 같습니다. 홀수만 표현하도록 조정되어 메모리 소비를 줄입니다. 그러나 이 접근 방식에는 여전히 5의 배수에 대한 불필요한 비트가 포함되어 있습니다.

최적화된 알고리즘

에서 제안한 보다 효율적인 알고리즘입니다. AKS는 일반적인 경우에 대해 가장 빠른 소수 테스트를 제공하지만 제한된 범위에서 소수를 찾는 데는 적합하지 않을 수 있습니다.

Python 구현

실용적인 목적으로는 Python 구현을 사용할 수 있습니다.

<code class="python">def isprime(n):
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True</code>

이 알고리즘은 소수(2와 3 제외)가 6k - 1 또는 6k 1 형식이라는 사실을 활용합니다. 이러한 형식의 제수만 검색합니다.

추가 옵션

속도를 위해 페르마의 정리에 기반한 유사 소수 테스트를 사용할 수 있습니다. 특히 범위가 제한적인 경우에는 거짓양성(카마이클 수)을 미리 계산합니다. ) 이진 검색을 활용하여 속도를 더욱 향상시킬 수 있습니다.

위 내용은 제한된 범위 내에서 소수를 어떻게 효율적으로 매핑할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!