Cela peut-il être plus pythonique?
Question
Je suis tombé sur ce programme simple (vraiment) il y a un certain temps. Il produit juste les premiers nombres premiers x. Je suis gêné de demander, est-il un moyen de le rendre plus « pythonique », à savoir condenser tout en le rendant (plus) lisible? Fonctions de commutation est très bien; Je suis seulement intéressé par la lecture.
Merci
from math import sqrt
def isprime(n):
if n ==2:
return True
if n % 2 ==0 : # evens
return False
max = int(sqrt(n))+1 #only need to search up to sqrt n
i=3
while i <= max: # range starts with 3 and for odd i
if n % i == 0:
return False
i+=2
return True
reqprimes = int(input('how many primes: '))
primessofar = 0
currentnumber = 2
while primessofar < reqprimes:
result = isprime(currentnumber)
if result:
primessofar+=1
print currentnumber
#print '\n'
currentnumber += 1
La solution
Votre algorithme lui-même peut être mis en œuvre pythonically, mais il est souvent utile de réécrire les algorithmes de manière fonctionnelle -. Vous pourriez vous retrouver avec une solution complètement différente mais plus lisible du tout (ce qui est encore plus pythonique)
def primes(upper):
n = 2; found = []
while n < upper:
# If a number is not divisble through all preceding primes, it's prime
if all(n % div != 0 for div in found):
yield n
found.append( n )
n += 1
Utilisation:
for pr in primes(1000):
print pr
Ou, avec le commentaire de Alasdair pris en compte, une version plus efficace:
from math import sqrt
from itertools import takewhile
def primes(upper):
n = 2; foundPrimes = []
while n < upper:
sqrtN = int(sqrt(n))
# If a number n is not divisble through all preceding primes up to sqrt(n), it's prime
if all(n % div != 0 for div in takewhile(lambda div: div <= sqrtN, foundPrimes)):
yield n
foundPrimes.append(n)
n += 1
Autres conseils
Le code donné n'est pas très efficace. Autre solution (comme inefficace): †
>>> from math import sqrt
>>> def is_prime(n):
... return all(n % d for d in range(2, int(sqrt(n)) + 1))
...
>>> def primes_up_to(n):
... return filter(is_prime, range(2, n))
...
>>> list(primes_up_to(20))
[2, 3, 5, 7, 11, 13, 17, 19]
Ce code utilise all
, range
, int
, math.sqrt
, filter
et list
. Il est pas tout à fait identique à votre code, car il imprime les nombres premiers jusqu'à un certain nombre, pas exactement n nombres premiers. Pour cela, vous pouvez faire:
>>> from itertools import count, islice
>>> def n_primes(n):
... return islice(filter(is_prime, count(2)), n)
...
>>> list(n_primes(10))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Cela introduit deux autres fonctions, à savoir itertools.count
itertools.islice
. (Ce dernier morceau de code ne fonctionne que dans Python 3.x, en Python 2.x, utilisez itertools.ifilter
au lieu de filter
.)
† : Une méthode plus efficace est d'utiliser le crible d'Eratosthène .
Tout d'abord, vous ne devez pas assigner à une variable maximum car il est une fonction intégrée utilisée pour trouver la valeur maximale d'un itérable. En outre, cette section entière du code peut plutôt être écrit comme
for i in xrange(3, int(sqrt(n))+1, 2):
if n%i==0: return False
En outre, au lieu de définir un nouveau résultat variable et mettre la valeur retournée par isprime en elle, vous pouvez simplement faire directement
if isprime(currentnumber):
J'ai récemment trouvé solutions Projet d'Euler python fonctionnel et il a quelques exemples vraiment sympa de travailler avec nombres premiers comme celui-ci. numéro 7 est assez proche de votre problème:
def isprime(n):
"""Return True if n is a prime number"""
if n < 3:
return (n == 2)
elif n % 2 == 0:
return False
elif any(((n % x) == 0) for x in xrange(3, int(sqrt(n))+1, 2)):
return False
return True
def primes(start=2):
"""Generate prime numbers from 'start'"""
return ifilter(isprime, count(start))
En général, vous ne l'utilisez pas en boucles pour des choses simples comme celui-ci. Vous créez plutôt un objet de plage et obtenir les éléments à partir de là. Ainsi, vous pouvez réécrire la première boucle à ceci par exemple:
for i in range( 3, int( sqrt( n ) ) + 1, 2 ): if n % i == 0: return False
Et ce serait beaucoup mieux si vous cache vos nombres premiers et seulement vérifier les nombres premiers précédents lors de la vérification d'un nouveau numéro. Vous pouvez économiser beaucoup de temps par là (et calculer facilement un plus grand nombre de choix de cette façon). Voici un code que j'ai écrit avant d'obtenir tous les nombres premiers jusqu'à n
facilement:
def primeNumbers ( end ): primes = [] primes.append( 2 ) for i in range( 3, end, 2 ): isPrime = True for j in primes: if i % j == 0: isPrime = False break if isPrime: primes.append( i ) return primes print primeNumbers( 20 )
Traduit des gars brillants à stacktrace.it ( Daniele Varrazzo, en particulier), cette version profite de binaire min-tas pour résoudre ce problème :
from heapq import heappush, heapreplace
def yield_primes():
"""Endless prime number generator."""
# Yield 2, so we don't have to handle the empty heap special case
yield 2
# Heap of (non-prime, prime factor) tuples.
todel = [ (4, 2) ]
n = 3
while True:
if todel[0][0] != n:
# This number is not on the head of the heap: prime!
yield n
heappush(todel, (n*n, n)) # add to heap
else:
# Not prime: add to heap
while todel[0][0] == n:
p = todel[0][1]
heapreplace(todel, (n+p, p))
# heapreplace pops the minimum value then pushes:
# heap size is unchanged
n += 1
Ce code est pas à moi et je ne comprends pas bien ( mais est ici explaination :)), donc je marquer cette réponse comme communauté wiki.
Vous pouvez le rendre plus pythonique avec l'algorithme de tamis (tous les nombres premiers petits que 100):
def primes(n):
sieved = set()
for i in range(2, n):
if not(i in sieved):
for j in range(i + i, n, i):
sieved.add(j)
return set(range(2, n)) - sieved
print primes(100)
Un truc très petit va tourner à votre objectif.