Can this be made more pythonic?
I came across this (really) simple program a while ago. It just outputs the first x primes. I'm embarrassed to ask, is there any way to make it more "pythonic" ie condense it while making it (more) readable? Switching functions is fine; I'm only interested in readability.
Thanks
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 开发者_如何学JAVA= 2
while primessofar < reqprimes:
result = isprime(currentnumber)
if result:
primessofar+=1
print currentnumber
#print '\n'
currentnumber += 1
Your algorithm itself may be implemented pythonically, but it's often useful to re-write algorithms in a functional way - You might end up with a completely different but more readable solution at all (which is even more pythonic).
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
Usage:
for pr in primes(1000):
print pr
Or, with Alasdair's comment taken into account, a more efficient version:
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
The given code is not very efficient. Alternative solution (just as inefficient):†
>>> 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]
This code uses all, range, int, math.sqrt, filter and list. It is not completely identical to your code, as it prints primes up to a certain number, not exactly n primes. For that, you can do:
>>> 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]
That introduces another two functions, namely itertools.count and itertools.islice. (That last piece of code works only in Python 3.x; in Python 2.x, use itertools.ifilter instead of filter.)
†: A more efficient method is to use the Sieve of Eratosthenes.
A few minor things from the style guide.
n ==2: => n == 2:
currentnumber => current_numberFirstly, you should not assign max to a variable as it is an inbuilt function used to find the maximum value from an iterable. Also, that entire section of code can instead be written as
for i in xrange(3, int(sqrt(n))+1, 2):
if n%i==0: return False
Also, instead of defining a new variable result and putting the value returned by isprime into it, you can just directly do
if isprime(currentnumber):
I recently found Project Euler solutions in functional python and it has some really nice examples of working with primes like this. Number 7 is pretty close to your problem:
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))
Usually you don't use while loops for simple things like this. You rather create a range object and get the elements from there. So you could rewrite the first loop to this for example:
for i in range( 3, int( sqrt( n ) ) + 1, 2 ):
if n % i == 0:
return False
And it would be a lot better if you would cache your prime numbers and only check the previous prime numbers when checking a new number. You can save a lot time by that (and easily calculate larger prime numbers this way). Here is some code I wrote before to get all prime numbers up to n easily:
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 )
Translated from the brilliant guys at stacktrace.it (Daniele Varrazzo, specifically), this version takes advantage of a binary min-heap to solve this problem:
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
This code isn't mine and I don't understand it fully (but the explaination is here :) ), so I'm marking this answer as community wiki.
You can make it more pythonic with sieve algorithm (all primes small than 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)
A very small trick will turn it to your goal.
加载中,请稍侯......
精彩评论