Trovare Primes con modulo in Python

Question

ho sudato su questo pezzo di codice - che restituisce tutti i numeri primi in una lista:

primes = range(2, 20) 
for i in range(2, 8): 
    primes = filter(lambda x: x == i or x % i, primes) 

print primes 

Funziona ... ma io non capisco il ruolo " x == i or x % i "suona nel complesso.

anche io non capisco perché il secondo intervallo è solo 2 a 7.

Ho anche creato un'implementazione di Python del crivello di Eratostene, nella speranza che mi possa dare una certa comprensione, ma non lo ha fatto.

Quando rimuovo la componente x % i, mi sarei aspettato questo codice di darmi i numeri comuni a entrambi i set, ma non:

nums = [2, 20] 
for i in range(2, 8): 
    nums = filter(lambda x: x == i, nums) 

print nums 

perché è questo?

Allo stesso modo, quando rimuovo la componente x == i, restituisce i numeri primi da 11 a 19.

nums = range(2, 20) 

for i in range(2, 8): 
    nums = filter(lambda x: x % i, nums) 

print nums 

Anche in questo caso, non capisco il motivo per cui ignora tutti i primi sotto 11.

Successivo , Ho provato questo:

nums = [13] 

for i in range(2, 8): 
    nums = filter(lambda x: x % i, nums) 

print nums 

Ancora, questo non ha senso per me. Il lambda sta iterando su x in nums corretto? E i sta iterando nell'intervallo da 2 a 7. Quindi, non stiamo prendendo 13 % i ... da 2 a 7? Come si traduce in "13"?

Utilizzando la stessa logica di immediatamente sopra, ho fatto la stessa cosa con "13", ma utilizzando x == i nella lambda.

for i in range(2, 8): 
    nums = filter(lambda x: x == i, nums) 

print nums 

E come mi aspettavo, è restituito un elenco vuoto - che ha un senso nella mia mente, perché 13 non appare mai nel range di 2 a 7.

Per riferimento per chiunque cerchi di aiutare, questa è la mentalità sono in quando lavoro con filter() e lambda:

a = range (1, 11) 
b = range (9, 20) 

for i in filter(lambda x: x in a, b): 
    print i, 

questo, naturalmente, noi "9 10" dà. So che la struttura del loop è diversa, ma spero che ti aiuti a vedere dove si trova la mia confusione.

Ho lavorato con filter() e lambda in modo un po 'estensivo, quindi ho pensato di poterlo capire, ma sono perplesso! Spero solo che la risposta non sia così ovvia e ovvia che mi sento un idiota ...

Answer 1

Sembra una compatta (ma un po 'oscura) attuazione del crivello di Eratostene [EDIT: come sottolineato nei commenti, questo è in effetti un "setaccio infedele" poiché la divisione di prova causa worse time complexity rispetto al setaccio effettivo di Eratostene].

La prima riga è solo un intervallo di ricerca arbitrario di numeri interi consecutivi per filtrare numeri primi:

primes = range(2, 20) 

Successiva, following the sieve algorithm, iteriamo con integer i in range (2, n), dove n è ingenuamente il più grande numero nell'intervallo di ricerca (anche se in questo caso, 7 è il limite superiore scelto - più su questo sotto).

for i in range(2, 8): 
    primes = filter(lambda x: x == i or x % i, primes) 

Gli stati algoritmo che abbiamo includono I ed escludere multipli di I. Questo è ciò che la lambda predicati filtro -

• includono i: x == 1
• escludono multipli di i: x % i - questo è l'abbreviazione di mano per x % i != 0. In altre parole, x non è divisibile per i, o in alternativa, x non è un multiplo di i.

Il limite superiore di 8 sembra un po 'arbitraria - in minima parte, abbiamo solo bisogno di cercare fino a sqrt(n), in quanto significa che sqrt(n) * sqrt(n) = nsqrt(n) è un limite superiore dello spazio di ricerca.

La radice quadrata di 19 è circa 4,4, e in questo esempio si vede che l'elenco dei numeri primi non cambia dopo i = 3.

In [18]: primes = range(2, 20) 

In [19]: for i in range(2, 8): 
    ....:  primes = filter(lambda x: x == i or x % i, primes) 
    ....:  print i, primes 
    ....: 
2 [2, 3, 5, 7, 9, 11, 13, 15, 17, 19] 
3 [2, 3, 5, 7, 11, 13, 17, 19] 
4 [2, 3, 5, 7, 11, 13, 17, 19] 
5 [2, 3, 5, 7, 11, 13, 17, 19] 
6 [2, 3, 5, 7, 11, 13, 17, 19] 
7 [2, 3, 5, 7, 11, 13, 17, 19] 

Answer 2

Penso che la risposta sia abbastanza semplice. Aumenta il tuo set di numeri primi dal range (2,20) al range (2,30) e prova di nuovo il tuo esperimento mentale. Mi renderà molto più ovvio.

la funzione di filtro restituirà i valori per la gamma di gamma (2,20) che i

filter(lambda x: x == i or x % i, primes) 

restituisce true.

Oltre ad aumentare i numeri primi da intervallo (2,20) a intervallo (2,30), giocare con i criteri del filtro interno e inizierai a vedere le differenze che stai cercando.

#!/usr/bin/python 

primes = range(2, 30) 
for i in range(2, 3): 
    primes = filter(lambda x: x == i or x % i, primes) 

print primes 

che si traduce in:

[2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29] 

e

#!/usr/bin/python 

primes = range(2, 30) 
for i in range(2, 4): 
    primes = filter(lambda x: x == i or x % i, primes) 

print primes 

risultati in

[2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29] 

Answer 3

Il primo blocco di codice che hai postato è l'esempio più facile per me spiegare questo :

primes = range(2, 20) 
for i in range(2, 8): 
    primes = filter(lambda x: x == i or x % i, primes) 
print primes 

Quando si utilizza il metodo Sieve of Eratosthenes, la cosa importante da notare è che hai solo per togliere i numeri che sono i prodotti di numeri fino alla radice quadrata del max. L'uso di range(2,8) sopra implementa questo (va da 2 a 7, che è più del necessario). La radice quadrata di 19 (il numero più alto nell'intervallo esterno controllato) è tra 4 e 5. Quindi il numero più alto che deve essere controllato nell'intervallo è 4 (dobbiamo solo controllare gli interi).

Usando questa conoscenza, si potrebbe migliorare il codice per essere come segue (questo trova i numeri primi < = 19):

import math 
max = 19 #Set it here 
max += 1 
primes = range(2, max) 
for i in range(2, int(math.ceil(math.sqrt(max)))): 
    primes = filter(lambda x: x == i or x % i, primes) 
print primes 

Nota che invece di utilizzare floor e poi aggiungendo uno perché range è esclusivo, io uso ceil.

Run qui: http://repl.it/8N8

Edit: ho anche capito questo (e il codice fornito in questione) non è una completa implementazione del metodo setaccio, dal momento che secondo l'algoritmo, dovremmo solo multipli di bandiera di numeri primi, il che significa che l'uso interno di range non è efficiente come dovrebbe essere.

Consulta l'illustrazione grafica dell'algoritmo in corso:

Answer 4

ho scritto un elenco semplice di comprensione per generare numeri primi . Ovviamente l'idea principale è stata copiata nello stack overflow. Ad essere onesti, mi ci è voluto del tempo per capirlo dato che ero un principiante in pitone. Ho usato questa lista di comprensione per chiamando una funzione lambda separatamente. Quindi, prima discuterò la funzione lambda.

funzione lambda: is_prime = lambda x: tutti (! X% y = 0 per y in range (2, int (Math.sqrt (x)) + 1))

Ora la lista comprensione usando il lambda di cui sopra.

numeri primi = [x per x nella gamma (30) se is_prime (x) == true]