Comment générer efficacement un flux infini de nombres premiers en Python ?

Comment implémenter un générateur infini efficace de nombres premiers en Python ?

Un moyen efficace de générer une série infinie de nombres premiers est d'utiliser le tamis d'Eratosthène, qui élimine les nombres non premiers en marquant de manière itérative leurs multiples. Bien que cette méthode soit efficace, elle nécessite beaucoup de mémoire pour stocker les nombres marqués.

erat2

Voici la fonction erat2 du livre de recettes de la bibliothèque standard de Python, qui peut être utilisé pour générer une série infinie de nombres premiers numéros :

import itertools as it
def erat2( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

erat2a

La fonction erat2 peut être encore optimisée en évitant les vérifications inutiles :

import itertools as it
def erat2a( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

erat3

Pour des performances encore plus rapides, la fonction erat3 profite du fait que tous les nombres premiers (sauf 2, 3 et 5) modulo 30 ne donne que huit nombres spécifiques. Cela réduit considérablement le nombre de contrôles nécessaires pendant le processus de tamisage :

import itertools as it
def erat3( ):
    D = { 9: 3, 25: 5 }
    yield 2
    yield 3
    yield 5
    MASK= 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0,
    MODULOS= frozenset( (1, 7, 11, 13, 17, 19, 23, 29) )

    for q in it.compress(
            it.islice(it.count(7), 0, None, 2),
            it.cycle(MASK)):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = q + 2*p
            while x in D or (x%30) not in MODULOS:
                x += 2*p
            D[x] = p

Ces optimisations peuvent entraîner des améliorations significatives des performances, en particulier lors de la génération de grands nombres premiers.

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!