Qualcuno può forse insegnarmi come ottimizzare ulteriormente questo script "stampa fino all'ennesimo numero primo"?

Question

Ho 17 anni per iniziare a programmare con l'aiuto del linguaggio di programmazione Python.

Ho cercato di ottimizzare questo algoritmo, forse eliminando uno dei loop, o con un test migliore per verificare i numeri primi.

Tentando di calcolare e visualizzare 100000 numeri primi, lo script fa una pausa di circa 6 secondi mentre popola la lista con i primi prima che l'elenco di primi venga restituito alla console come output.

ho avuto modo di sperimentare con l'utilizzo di

print odd, 

stampare semplicemente ogni numero primo scoperto, che è più veloce per gli ingressi più piccoli, come n = 1000, ma per n = 1000000 lista stessa stamperà molto più veloce (sia nella shell python e nella console).

Forse l'intero codice/algoritmo dovrebbe essere rinnovato, ma lo script dovrebbe rimanere essenzialmente lo stesso: l'utente digita il numero di numeri primi da stampare (n) e lo script restituisce tutti i numeri primi fino all'ennesimo primo numero.

from time import time 
odd = 1 
primes = [2] 
n = input("Number of prime numbers to print: ") 
clock = time() 
def isPrime(number): 
    global primes 
    for i in primes: 
     if i*i > number: 
      return True 
     if number%i is 0: 
      return False 
while len(primes) < n: 
    odd += 2 
    if isPrime(odd): 
     primes += [odd] 
print primes 
clock -= time() 
print "\n", -clock 
raw_input() 

potrei desiderare di riscrivere l'intero script per utilizzare un setaccio come il crivello di Atkin: http://en.wikipedia.org/wiki/Sieve_of_Atkin

Tuttavia, io sono semplicemente un principiante in Python (o anche a programmazione: ho iniziato a scrivere solo il 2 codice settimane fa) e sarebbe una vera sfida per me capire come codificare un algoritmo di Sieve of Atkin in Python.

auguro un hacker google fuori ci sarebbe mano hold me attraverso cose come questa :(

Answer 1

Uno semplici ottimizzazioni che potrebbero essere applicate senza l'hacking completamente il codice.

• l'i * i su ogni Prime diventa molto dispendioso come la lista si allunga. Invece calcolare la radice quadrata dei di fuori del ciclo e il test contro questo valore all'interno del ciclo.

come mai radice quadrata è essa stessa e calcolo costoso e la maggior parte dei numeri candidati sarà rifiutata come divisibile da uno dei numeri primi inferiori (3,5,7), quindi non risulta essere una buona ottimizzazione (pessimizzazione?). Ma in realtà non abbiamo bisogno di essere così precisi e un semplice controllo che il primo sia meno di un terzo del valore ha un effetto simile senza il costo computazionale del calcolo della radice quadrata, ma, a scapito di un numero relativamente basso di inutili test.

Answer 2

Si potrebbe usare prime sieve, e con un semplice tocco:

1. Definire il primo numero primo 2 come si fa, impostare il maggior numero raggiunto (max) a 2;
2. Generare un elenco di numeri progressivi n da max+1 a max+n;
3. Utilizzare il setaccio con i numeri primi in questo elenco. Quando si setaccia, impostare il numero iniziale di ciascun numero primo sul numero più piccolo nell'elenco che potrebbe essere diviso per il primo;
4. Se l'importo non è reacher, vai a 2.

In questo modo, è possibile controllare la lunghezza dell'elenco e man mano che la lunghezza aumenta, la velocità sarà più veloce. Tuttavia, questa è una rielaborazione totale dell'algoritmo ed è più difficile da programmare.

Ecco un esempio di codice, che è abbastanza grezza, ma questo richiede solo il tempo meno del 70% di quella originale:

from math import sqrt 
from time import time 
primes = [2] 
max = 3 
n = input("Number of prime numbers to print: ") 
r=2 
clock = time() 
def sieve(r): 
    global primes 
    global max 
    s = set(range(max,max+r)) 
    for i in primes: 
     b=max//i 
     if (b*i<max): 
      b=b+1 
     b=b*i 
     while b<=max+r-1: 
      if b in s: 
       s.remove(b) 
      b=b+i 
    for i in s: 
     primes.append(i) 
while len(primes) < n: 
    r=primes[-1] 
    sieve(r) 
    max=max+r 
primes=primes[0:n] 
print primes 
clock -= time() 
print "\n", -clock 
raw_input() 

Ci sono molti modi per migliorare questo, questo dimostra solo il concetto di approccio .

Inoltre, questo può far esplodere la memoria quando il numero è grande. Ho usato il limite dinamico per cercare di alleggerirlo in qualche modo.

E se sei davvero curioso (e senza paura), puoi guardare le implementazioni più complicate in vari progetti open source. Un esempio è Pari/GP, che è scritto in C++, ed è molto veloce (ho provato da 1 a 50000000 in meno di 1 minuto, se non ricordo male). Traducendoli in Python potrebbe essere difficile, ma sarà utile, forse non solo per te ;-)

Answer 3

Qualsiasi numero che termini in 5, tranne 5, non è un numero primo. Quindi puoi inserire un'istruzione che salta qualsiasi numero che termina con 5 maggiore di 5.

Answer 4

Come già detto da Ziyao Wei, avrei anche provato un'implementazione di Sieve. L'unica cosa che migliorerei è usare il Prime number theorem come punto di partenza per la dimensione usata.

Calcolare la funzione inversa non è semplice in puro pitone, ma un approccio iterativo dovrebbe essere abbastanza buono e in questo modo si potrebbe avere una buona idea di quanto sarebbe grande il setaccio. Dato che non ricordo veramente le dimostrazioni per il teorema in dettaglio e sono le 6 del mattino qui, qualcun altro dovrà intervenire per dire se il teorema garantisce un certo limite superiore che potrebbe essere usato per consentire l'uso del semplice setaccio senza doversi preoccupare di coltivarlo Iirc purtroppo non è il caso.

Answer 5

Come già accennato, l'algoritmo presentato non può essere migliorato in modo significativo. Se viene richiesta una soluzione rapida, il setaccio Eratostene è appropriato. La dimensione x del setaccio può essere estimated utilizzando n >= x/(ln x + 2) se x >= 55. Questa equazione può essere risolta usando l'iterazione di Newton. L'algoritmo presentato è circa 10 volte più veloce dell'originale:

def sieveSize(n): 
    # computes x such that pi(x) >= n (assumes x >= 55) 
    x = 1.5 * n # start 
    y = x - n * math.log(x) - 2 * n 
    while abs(y) > 0.1: 
     derivative = 1 - n/x 
     x = x - y/derivative 
     y = x - n * math.log(x) - 2 * n 
    return int(x) + 1 

def eratosthenes(n): 
    # create a string flags: flags[i]=='1' iff i prime 
    size = sieveSize(n) 
    flags = ['1'] * size # start with: all numbers are prime 
    flags[0] = flags[1] = '0' # 0 and 1 are not primes 
    i = 0 
    while i * i < size: 
     if flags[i] == '1': 
      for j in range(i * i, size, i): 
       flags[j] = '0' 
     i += 1 
    return flags 

def primes(n): 
    flags = eratosthenes(n) 
    prims = [] 
    for i in range(0, len(flags)): 
     if flags[i] == '1': 
      prims.append(i) 
    return prims 

prims = primes(100000)