Maison >développement back-end >Tutoriel Python >Comment générer efficacement un flux infini de nombres premiers en Python ?

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

Linda Hamilton
Linda Hamiltonoriginal
2024-12-06 21:55:16473parcourir

How to Efficiently Generate an Infinite Stream of Prime Numbers in 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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn