Le tamis d'Eratosthène - Trouver les nombres premiers Python

Question

Juste pour clarifier, ce n'est pas un problème de devoir :)

Je voulais trouver des nombres premiers pour une application mathématique que je suis en train de créer et je suis tombé sur Le tamis d'Eratosthène approche.

J'en ai écrit une implémentation en Python. Mais c'est terriblement lent. Par exemple, si je veux trouver tous les nombres premiers inférieurs à 2 millions. Cela prend > 20 minutes. (Je l'ai arrêté à ce stade). Comment puis-je accélérer le processus ?

def primes_sieve(limit):
    limitn = limit+1
    primes = range(2, limitn)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)
    return primes

print primes_sieve(2000)

UPDATE : J'ai fini par faire du profilage sur ce code et j'ai constaté que beaucoup de temps était passé à retirer un élément de la liste. C'est assez compréhensible si l'on considère qu'il faut parcourir toute la liste (dans le pire des cas) pour trouver l'élément, le supprimer, puis réajuster la liste (peut-être qu'il y a des copies ?). Bref, j'ai remplacé la liste par le dictionnaire. Ma nouvelle implémentation -

def primes_sieve1(limit):
    limitn = limit+1
    primes = dict()
    for i in range(2, limitn): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False
    return [i for i in primes if primes[i]==True]

print primes_sieve1(2000000)

Answer 1

Vous n'implémentez pas tout à fait le bon algorithme :

Dans votre premier exemple, primes_sieve ne maintient pas une liste de drapeaux de primalité à activer/désactiver (comme dans l'algorithme), mais redimensionne une liste d'entiers de façon continue, ce qui est très coûteux : enlever un élément d'une liste nécessite de décaler tous les éléments suivants d'une unité.

Dans le deuxième exemple, primes_sieve1 maintient un dictionnaire de drapeaux de primalité, ce qui est un pas dans la bonne direction, mais il itère sur le dictionnaire dans un ordre indéfini, et élimine de manière redondante les facteurs de facteurs (au lieu de seulement les facteurs de nombres premiers, comme dans l'algorithme). Vous pouvez résoudre ce problème en triant les clés et en ignorant les non-primes (ce qui accélère déjà le processus d'un ordre de grandeur), mais il est toujours beaucoup plus efficace d'utiliser directement une liste.

L'algorithme correct (avec une liste au lieu d'un dictionnaire) ressemble à quelque chose comme ça :

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in xrange(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

(Notez que cela inclut également l'optimisation algorithmique consistant à commencer le marquage de la non-prime à la case de la prime ( i*i ) au lieu de son double).

Answer 2

def eratosthenes(n):
    multiples = []
    for i in range(2, n+1):
        if i not in multiples:
            print (i)
            for j in range(i*i, n+1, i):
                multiples.append(j)

eratosthenes(100)

Answer 3

Le retrait du début d'un tableau (liste) nécessite de déplacer vers le bas tous les éléments qui le suivent. Cela signifie que retirer chaque élément d'une liste de cette manière en commençant par le début est une opération O(n^2).

Vous pouvez le faire beaucoup plus efficacement avec des séries :

def primes_sieve(limit):
    limitn = limit+1
    not_prime = set()
    primes = []

    for i in range(2, limitn):
        if i in not_prime:
            continue

        for f in range(i*2, limitn, i):
            not_prime.add(f)

        primes.append(i)

    return primes

print primes_sieve(1000000)

... ou alternativement, éviter de devoir réorganiser la liste :

def primes_sieve(limit):
    limitn = limit+1
    not_prime = [False] * limitn
    primes = []

    for i in range(2, limitn):
        if not_prime[i]:
            continue
        for f in xrange(i*2, limitn, i):
            not_prime[f] = True

        primes.append(i)

    return primes

Answer 4

Je me rends compte que cela ne répond pas vraiment à la question de savoir comment générer des nombres premiers rapidement, mais peut-être que certains trouveront cette alternative intéressante : parce que python fournit une évaluation paresseuse via des générateurs, le crible d'Eratosthène peut être implémenté exactement comme indiqué :

def intsfrom(n):
    while True:
        yield n
        n += 1

def sieve(ilist):
    p = next(ilist)
    yield p
    for q in sieve(n for n in ilist if n%p != 0):
        yield q

try:
    for p in sieve(intsfrom(2)):
        print p,

    print ''
except RuntimeError as e:
    print e

Le bloc try est là parce que l'algorithme s'exécute jusqu'à ce qu'il explose la pile et sans le bloc try, le backtrace est affiché. le bloc try, le backtrace est affiché en poussant la sortie réelle que vous voulez voir hors écran.