Comment pouvons-nous cartographier efficacement les nombres premiers dans une plage limitée ?

Cartographie efficace des nombres premiers dans une plage limitée

Dans le domaine de l'informatique, l'identification des nombres premiers dans une plage spécifique est une tâche courante . L'objectif est de créer une structure de données qui mappe efficacement les nombres à leur statut « est premier ».

Une approche consiste à utiliser une fonction booléenne isprime(n). Cependant, pour une consommation de mémoire optimale, une structure de données personnalisée est souhaitable. Pour une plage (1, N], où N est une constante, les considérations suivantes sont essentielles :

Variation du tamis d'Ératosthène

Le tamis classique d'Ératosthène pourrait être adapté pour représenter uniquement les nombres impairs, réduisant ainsi la consommation de mémoire. Cependant, cette approche inclut toujours des bits inutiles pour les multiples de cinq.

Algorithme optimisé

Un algorithme plus efficace proposé par AKS fournit le test d'amorce le plus rapide pour les cas généraux. Cependant, il peut ne pas être adapté pour trouver des nombres premiers dans une plage limitée.

Implémentation de Python

À des fins pratiques, un L'implémentation Python est disponible :

<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>

Cet algorithme utilise le fait que les nombres premiers (autres que 2 et 3) sont de la forme 6k - 1 ou 6k 1. Il recherche uniquement les diviseurs de ces formes.

Options supplémentaires

Pour la vitesse, un test pseudo-premier basé sur le théorème de Fermat peut être utilisé, en particulier lorsque la plage est limitée. Cependant, le précalcul des faux positifs (nombres de Carmichael. ) peut encore améliorer la vitesse en tirant parti de la recherche binaire.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!