Crible d'Eratosthène - Trouver Python nombres premiers

Question

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

Je voulais trouver des nombres premiers pour une application mathématique je construis et suis tombé sur Crible d'Eratosthène < approche / strong> .

J'ai écrit une implémentation de Python en. Mais il est terriblement lent. Pour dire, si je veux trouver tous les nombres premiers moins de 2 millions d'euros. Il faut> 20 minutes. (Je me suis arrêté à ce stade). Comment puis-je accélérer ce?

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)

Mise à jour: J'ai fini par faire le profilage sur ce code et a constaté que beaucoup de temps a été consacré à la suppression d'un élément de la liste. Tout à fait compréhensible étant donné qu'il doit traverser pour trouver l'élément et puis supprimez toute la liste (pire cas), puis Réajuster la liste (peut-être une copie continue?). Quoi qu'il en soit, je lançai sur la liste pour le dictionnaire. Ma nouvelle mise en œuvre -

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'êtes pas tout à fait réaliser l'algorithme correct:

Dans votre premier exemple, primes_sieve ne maintient pas une liste des drapeaux de primalité de grève / unset (comme dans l'algorithme), mais redimensionné à la place une liste d'entiers en continu, ce qui est très cher: la suppression d'un élément dans une liste nécessite décaler tous les articles suivants par une.

Dans le second 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 pour non défini, et les grèves de manière redondante les facteurs de facteurs ( au lieu de seulement les facteurs de nombres premiers, comme dans l'algorithme). Vous pouvez corriger cela en triant les clés, et sauter les non-nombres premiers (ce qui en fait déjà un ordre de grandeur plus rapide), mais il est encore beaucoup plus efficace d'utiliser simplement une liste directement.

L'algorithme correct (avec une liste à la place d'un dictionnaire) ressemble à quelque chose comme:

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 range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

(Notez que ceci inclut également l'optimisation algorithmique de démarrage du marquage non-prime à la place du premier (de 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

Suppression du début d'un tableau (liste) exige de déplacer tous les éléments après le bas. Cela signifie que la suppression de tous les éléments d'une liste de cette manière à partir de l'avant est une opération O (n ^ 2).

Vous pouvez faire beaucoup plus efficacement avec des jeux:

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 bien, éviter d'avoir à 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

Bien plus:

import time
def get_primes(n):
  m = n+1
  #numbers = [True for i in range(m)]
  numbers = [True] * m #EDIT: faster
  for i in range(2, int(n**0.5 + 1)):
    if numbers[i]:
      for j in range(i*i, m, i):
        numbers[j] = False
  primes = []
  for i in range(2, m):
    if numbers[i]:
      primes.append(i)
  return primes

start = time.time()
primes = get_primes(10000)
print(time.time() - start)
print(get_primes(100))

Answer 5

Je sais que cela ne répond pas vraiment à la question de la façon de générer des nombres premiers rapidement, mais peut-être certains trouveront cette alternative intéressante: car python fournit une évaluation paresseuse par des générateurs, tamis Eratosthène peut être mis en œuvre 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 les pistes de l'algorithme jusqu'à ce qu'il souffle la pile et sans essayez de bloquer le backtrace est affiché en poussant la sortie réelle que vous voulez voir hors de l'écran.

Answer 6

En combinant les contributions de nombreux amateurs (dont Glenn Maynard et MrHIDEn des commentaires ci-dessus), je suis venu avec la suite morceau de code en python 2:

def simpleSieve(sieveSize):
    #creating Sieve.
    sieve = [True] * (sieveSize+1)
    # 0 and 1 are not considered prime.
    sieve[0] = False
    sieve[1] = False
    for i in xrange(2,int(math.sqrt(sieveSize))+1):
        if sieve[i] == False:
            continue
        for pointer in xrange(i**2, sieveSize+1, i):
            sieve[pointer] = False
    # Sieve is left with prime numbers == True
    primes = []
    for i in xrange(sieveSize+1):
        if sieve[i] == True:
            primes.append(i)
    return primes

sieveSize = input()
primes = simpleSieve(sieveSize)

Le temps nécessaire pour le calcul sur ma machine pour différentes entrées en puissance de 10 est:

• 3: 0,3 ms
• 4: 2,4 ms
• 5: 23 ms
• 6: 0,26 de
• 7: 3.1 de
• 8: 33 de

Answer 7

Un hack de vitesse simple:. Lorsque vous définissez la variable « de nombres premiers, » mettre l'étape 2 pour sauter tous les numéros même automatiquement, et régler le point de départ à 1

Ensuite, vous pouvez optimiser par non pour i dans les nombres premiers, l'utilisation pour i en nombres premiers [: ronds (LEN (nombres premiers) ** 0,5)]. Cela augmentera considérablement les performances. De plus, vous pouvez éliminer les numéros se terminant par 5 à plus d'augmenter la vitesse.

Answer 8

Ma mise en œuvre:

import math
n = 100
marked = {}
for i in range(2, int(math.sqrt(n))):
    if not marked.get(i):
        for x in range(i * i, n, i):
            marked[x] = True

for i in range(2, n):
    if not marked.get(i):
        print i

Answer 9

Voici une version qui est un peu plus économe en mémoire (et: un tamis approprié, non divisions essai). En fait, au lieu de garder un tableau de tous les numéros, et biffant ceux qui ne sont pas premiers, ce qui maintient un tableau de compteurs - un pour chaque prime, il a découvert - et les-frogging bond en avant du premier putatif. De cette façon, il utilise le stockage proportionnel au nombre de nombres premiers, pas à au plus haut de premier choix.

import itertools

def primes():

    class counter:
        def __init__ (this,  n): this.n, this.current,  this.isVirgin = n, n*n,  True
            # isVirgin means it's never been incremented
        def advancePast (this,  n): # return true if the counter advanced
            if this.current > n:
                if this.isVirgin: raise StopIteration # if this is virgin, then so will be all the subsequent counters.  Don't need to iterate further.
                return False
            this.current += this.n # pre: this.current == n; post: this.current > n.
            this.isVirgin = False # when it's gone, it's gone
            return True

    yield 1
    multiples = []
    for n in itertools.count(2):
        isPrime = True
        for p in (m.advancePast(n) for m in multiples):
            if p: isPrime = False
        if isPrime:
            yield n
            multiples.append (counter (n))

Vous remarquerez que primes() est un générateur, donc vous pouvez garder les résultats dans une liste ou vous pouvez les utiliser directement. Voici les premiers nombres premiers de n:

import itertools

for k in itertools.islice (primes(),  n):
    print (k)

Et, pour être complet, voici une minuterie pour mesurer la performance:

import time

def timer ():
    t,  k = time.process_time(),  10
    for p in primes():
        if p>k:
            print (time.process_time()-t,  " to ",  p,  "\n")
            k *= 10
            if k>100000: return

Juste au cas où vous vous demandez, j'ai aussi écrit primes() comme un simple iterator (en utilisant __iter__ et __next__), et il a couru à peu près la même vitesse. Surpris moi aussi!

Answer 10

Je préfère NumPy à cause de la vitesse.

import numpy as np

# Find all prime numbers using Sieve of Eratosthenes
def get_primes1(n):
    m = int(np.sqrt(n))
    is_prime = np.ones(n, dtype=bool)
    is_prime[:2] = False  # 0 and 1 are not primes

    for i in range(2, m):
        if is_prime[i] == False:
            continue
        is_prime[i*i::i] = False

    return np.nonzero(is_prime)[0]

# Find all prime numbers using brute-force.
def isprime(n):
    ''' Check if integer n is a prime '''
    n = abs(int(n))  # n is a positive integer
    if n < 2:  # 0 and 1 are not primes
        return False
    if n == 2:  # 2 is the only even prime number
        return True
    if not n & 1:  # all other even numbers are not primes
        return False
    # Range starts with 3 and only needs to go up the square root
    # of n for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

# To apply a function to a numpy array, one have to vectorize the function
def get_primes2(n):
    vectorized_isprime = np.vectorize(isprime)
    a = np.arange(n)
    return a[vectorized_isprime(a)]

Vérifiez la sortie:

n = 100
print(get_primes1(n))
print(get_primes2(n))    
    [ 2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97]
    [ 2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97]

Comparer la vitesse du crible d'Eratosthène et la force brute sur ordinateur portable Jupyter. Tamiser d'Eratosthène en 539 fois plus vite que la force brute pour des millions d'éléments.

%timeit get_primes1(1000000)
%timeit get_primes2(1000000)
4.79 ms ± 90.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
2.58 s ± 31.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Answer 11

Je me suis dit qu'il doit être possible d'utiliser simplement la liste vide comme condition de terminaison pour la boucle et est venu avec ceci:

limit = 100
ints = list(range(2, limit))   # Will end up empty

while len(ints) > 0:
    prime = ints[0]
    print prime
    ints.remove(prime)
    i = 2
    multiple = prime * i
    while multiple <= limit:
        if multiple in ints:
            ints.remove(multiple)
        i += 1
        multiple = prime * i

Answer 12

import math
def sieve(n):
    primes = [True]*n
    primes[0] = False
    primes[1] = False
    for i in range(2,int(math.sqrt(n))+1):
            j = i*i
            while j < n:
                    primes[j] = False
                    j = j+i
    return [x for x in range(n) if primes[x] == True]

Answer 13

Ma plus rapide mise en œuvre:

isprime = [True]*N
isprime[0] = isprime[1] = False
for i in range(4, N, 2):
    isprime[i] = False
for i in range(3, N, 2):
    if isprime[i]:
        for j in range(i*i, N, 2*i):
            isprime[j] = False

Answer 14

Je pense que ce code est le plus court pour trouver des nombres premiers avec méthode Eratosthène

def prime(r):
    n = range(2,r)
    while len(n)>0:
        yield n[0]
        n = [x for x in n if x not in range(n[0],r,n[0])]


print(list(prime(r)))