Generatore di numeri primi di base in Python

Question

Volevo solo un feedback sul mio generatore di numeri primi. per esempio. è ok, usa molte risorse, ecc. Non usa librerie, è abbastanza semplice, ed è un riflesso del mio attuale stato di abilità di programmazione, quindi non ti trattenere come voglio imparare.

def prime_gen(n): 

    primes = [2] 
    a = 2 

    while a < n: 

     counter = 0 

     for i in primes: 
      if a % i == 0: 
       counter += 1 

     if counter == 0: 
      primes.append(a) 
     else: 
      counter = 0 

     a = a + 1 

    print primes 

Answer 1

Ci sono alcuni ottimizzazioni thar sono comuni:

Esempio:

def prime(x): 
    if x in [0, 1]: 
     return False 
    if x == 2: 
     return True 
    for n in xrange(3, int(x ** 0.5 + 1)): 
     if x % n == 0: 
      return False 
    return True 

• copertura casi di base
• Solo iterare fino alla radice quadrata di n

L'esempio precedente non genera numeri primi ma li verifica. Si potrebbe adattare gli stessi ottimizzazioni al codice :)

uno degli algoritmi più efficaci che ho trovato scritto in Python si trova nella risposta seguente domanda ans (usando un setaccio):

Simple Prime Generator in Python

mia adattamento dell'algoritmo vaglio:

from itertools import islice 


def primes(): 
    if hasattr(primes, "D"): 
     D = primes.D 
    else: 
     primes.D = D = {} 

    def sieve(): 
     q = 2 
     while True: 
      if q not in D: 
       yield q 
       D[q * q] = [q] 
      else: 
       for p in D[q]: 
        D.setdefault(p + q, []).append(p) 
       del D[q] 

      q += 1 

    return sieve() 


print list(islice(primes(), 0, 1000000)) 

il mio hardware posso generare il primo milione di numeri primi abbastanza rapidamente (g ato che questo è scritto in Python):

prologic@daisy 
Thu Apr 23 12:58:37 
~/work/euler 
$ time python foo.py > primes.txt 

real 0m19.664s 
user 0m19.453s 
sys 0m0.241s 

prologic@daisy 
Thu Apr 23 12:59:01 
~/work/euler 
$ du -h primes.txt 
8.9M primes.txt 

Answer 2

Ecco un generatore di numeri primi abbastanza efficiente che ho scritto un po 'indietro che utilizza il Sieve of Eratosthenes:

#!/usr/bin/env python2.7 

def primeslt(n): 
    """Finds all primes less than n""" 

    if n < 3: 
     return [] 

    A = [True] * n 
    A[0], A[1] = False, False 

    for i in range(2, int(n**0.5)+1): 
     if A[i]: 
      j = i**2 
      while j < n: 
       A[j] = False 
       j += i 

    return [num for num in xrange(n) if A[num]] 

def main(): 
    i = '' 
    while not i.isdigit(): 
     i = raw_input('Find all prime numbers less than... ') 
    print primeslt(int(i)) 

if __name__ == '__main__': 
    main() 

L'articolo di Wikipedia (linkato sopra) spiega come funziona meglio di quanto potrei, quindi ti raccomando di leggerlo.

Answer 3

Ecco il metodo standard di generazione di numeri primi adattate dal C# versione all'indirizzo: Most Elegant Way to Generate Prime Number

def prime_gen(n): 

    primes = [2] 

    # start at 3 because 2 is already in the list 
    nextPrime = 3 

    while nextPrime < n: 

     isPrime = True 

     i = 0 

     # the optimization here is that you're checking from 
     # the number in the prime list to the square root of 
     # the number you're testing for primality 
     squareRoot = int(nextPrime ** .5) 

     while primes[i] <= squareRoot: 

      if nextPrime % primes[i] == 0: 

       isPrime = False 

      i += 1 

     if isPrime: 

      primes.append(nextPrime) 

     # only checking for odd numbers so add 2 
     nextPrime += 2 

    print primes 

Answer 4

Ho alcune ottimizzazioni per il primo codice che può essere utilizzato quando l'argomento è negativo:

def is_prime(x):  
    if x <=1: 
     return False 
    else: 
     for n in xrange(2, int(x ** 0.5 + 1)): 
      if x % n == 0: 
       return False 
    return True 
print is_prime(-3) 

Answer 5

Essendo Python, di solito è meglio restituire un generatore che restituirà una sequenza infinita di numeri primi anziché una lista.

ActiveState ha una lista di anziani Crivello di Eratostene recipes

Qui è uno di loro aggiornato per Python 2.7 utilizzando itertools count con un argomento passo che non esisteva quando la ricetta originale è stato scritto:

import itertools as it 

def sieve(): 
    """ Generate an infinite sequence of prime numbers. 
    """ 
    yield 2 
    D = {} 
    for q in it.count(3, 2): # start at 3 and step by odds 
     p = D.pop(q, 0) 
     if p: 
      x = q + p 
      while x in D: x += p 
      D[x] = p   # new composite found. Mark that 
     else: 
      yield q   # q is a new prime since no composite was found 
      D[q*q] = 2*q 

Poiché si tratta di un generatore, è molto più efficiente in termini di memoria rispetto alla generazione di un intero elenco. Poiché individua il composito, è anche efficiente dal punto di vista computazionale.

Esegui questo:

>>> g=sieve() 

Poi ogni chiamata successiva torna il prossimo primo:

>>> next(g) 
2 
>>> next(g) 
3 
# etc 

È quindi possibile ottenere una lista tra i confini (vale a dire, il primo X dal primo al X + Y prime ...) utilizzando islice:

>>> tgt=0 
>>> tgt, list(it.islice(sieve(), tgt, tgt+10)) 
(0, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]) 
>>> tgt=1000000 
>>> tgt, list(it.islice(sieve(), tgt, tgt+10)) 
(1000000, [15485867, 15485917, 15485927, 15485933, 15485941, 15485959, 15485989, 15485993, 15486013, 15486041])