Can this be made more pythonic?

Question

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 = 2
while primessofar < reqprimes:

  result = isprime(currentnumber)

  if result:
     primessofar+=1
     print currentnumber
     #print '\n'

  currentnumber += 1

Answer 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

Answer 2

Firstly, 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):

Answer 3

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 )

Answer 4

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.

Answer 5

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.

Answer 6

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))