Comment déterminer le mappage principal le plus compact pour une plage (1, N) ?

Détermination de la cartographie principale compacte de manière optimale pour la plage (1, N)

Trouver la cartographie principale la plus compacte peut être une tâche difficile. L'algorithme idéal produirait une structure de données avec la consommation de mémoire la plus faible pour une plage spécifiée (1, N).

Une approche potentielle est l'algorithme AKS, considéré comme le plus rapide pour les tests principaux généraux. Pour les grands nombres premiers, l'exploration des nombres premiers avec des formes spéciales, telles que les nombres premiers de Mersenne, peut être bénéfique.

Cependant, pour les tests de nombres premiers à usage général dans une plage limitée, un algorithme plus pratique et plus efficace peut être utilisé :

<code class="python">def isprime(n):
    """Returns True if n is prime."""
    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 exploite le fait que les nombres premiers (sauf 2 et 3) sont de la forme 6k - 1 ou 6k 1. Il vérifie efficacement diviseurs dans cette plage, ce qui le rend approprié pour déterminer la primalité dans un intervalle spécifié.

Si la vitesse est primordiale et que la plage est bien définie, la mise en œuvre d'un test pseudo-premier basé sur le petit théorème de Fermat peut encore améliorer l'efficacité. Le précalcul des faux positifs (nombres de Carmichael) et l'utilisation de la recherche binaire offrent une approche encore plus rapide, mais cela s'accompagne de la limitation d'une plage restreinte.

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!