# Project Euler: primes in Python

This is a Python module I have just finished writing which I plan to use at Project Euler. Please let me know how I have done and what I could do to improve it.

# This constant is more or less an overestimate for the range in which
# n primes exist.  Generally 100 primes exist well within 100 * CONST numbers.
CONST = 20

def primeEval(limit):
''' This function yields primes using the
Sieve of Eratosthenes.

'''
if limit:
opRange = [True] * limit
opRange[0] = opRange[1] = False

for (ind, primeCheck) in enumerate(opRange):
if primeCheck:
yield ind
for i in range(ind*ind, limit, ind):
opRange[i] = False

def listToNthPrime(termin):
''' Returns a list of primes up to the nth
prime.
'''
primeList = []
for i in primeEval(termin * CONST):
primeList.append(i)
if len(primeList) >= termin:
break
return primeList

def nthPrime(termin):
''' Returns the value of the nth prime.

'''
primeList = []
for i in primeEval(termin * CONST):
primeList.append(i)
if len(primeList) >= termin:
break
return primeList[-1]

def listToN(termin):
''' Returns a list of primes up to the
number termin.
'''
return list(primeEval(termin))

def lastToN(termin):
''' Returns the prime which is both less than n
and nearest to n.

'''
return list(primeEval(termin))[-1]


# This constant is more or less an overestimate for the range in which
# n primes exist.  Generally 100 primes exist well within 100 * CONST numbers.
CONST = 20

def primeEval(limit):


Python convention says that functions should named lowercase_with_underscores

    ''' This function yields primes using the
Sieve of Eratosthenes.

'''
if limit:


What is this for? You could be trying to avoid erroring out when limit=0, but it seems to me that you still error at for limit=1.

        opRange = [True] * limit


As with functions, lowercase_with_underscore

        opRange[0] = opRange[1] = False

for (ind, primeCheck) in enumerate(opRange):


You don't need the parens around ind, primeCheck

            if primeCheck:
yield ind
for i in range(ind*ind, limit, ind):
opRange[i] = False

def listToNthPrime(termin):
''' Returns a list of primes up to the nth
prime.
'''
primeList = []
for i in primeEval(termin * CONST):
primeList.append(i)
if len(primeList) >= termin:
break
return primeList


You are actually probably losing out by attempting to stop the generator once you pass the number you wanted. You could write this as:

 return list(primeEval(termin * CONST))[:termin]


Chances are that you gain more by having the loop be in the loop function than you gain by stopping early.

def nthPrime(termin):
''' Returns the value of the nth prime.

'''
primeList = []
for i in primeEval(termin * CONST):
primeList.append(i)
if len(primeList) >= termin:
break
return primeList[-1]

def listToN(termin):
''' Returns a list of primes up to the
number termin.
'''
return list(primeEval(termin))

def lastToN(termin):
''' Returns the prime which is both less than n
and nearest to n.

'''
return list(primeEval(termin))[-1]


All of your functions will recalculate all the primes. For any sort of practical use you'll want to avoid that and keep the primes you've calculated.

• Are you suggesting that I just omit the loop within the functions nthPrime and listToNthPrime, or that I change the function primeEval to include a parameter which will allow it to terminate early? I just tested the calling functions without the loop. I was surprised the loop provides only 3% increase in speed. Also, what do you mean by "keep primes you've calculated"? – Jack J Feb 13 '13 at 23:39
• @JackJ, I'm suggesting you omit the loop. By keeping the primes, I mean that you should run sieve of erasthones once to find all the primes you need and use that data over and over again. – Winston Ewert Feb 13 '13 at 23:43
• @JackJ, store it in a variable. – Winston Ewert Feb 14 '13 at 0:57
• Sorry, but how would I reuse that data? By saving the output of the sieve to a file? Also, is the reason for omitting the loop to increase readability? – Jack J Feb 14 '13 at 0:58

General programming issues (non-Python specific):

• Avoiding duplicated code: listToNthPrime() and nthPrime() are identical beside the indexing. The later could be changed to def nthprime(termin): return listToNthPrime(termin)[-1]. But it can be argued if such a function is needed anyway, because indexing the first or last element of lists is such a basic usage that usually no further abstraction is necessary. So you could just replace you calls to nthPrime() by listToNthPrime()[-1]. The same is obviously also valid for listToN() and lastToN() in both senses. In fact you can just omit these functions.

• Naming: all identifier names should catch its purpose according to the abstraction level as precise they can (resulting clunky names are usually showing a need to refactor / change the abstraction). In that sense the name primeEval could be improved. "Eval" often is just too general to be really meaningful. iterPrimes() will work. Further it makes it clear that it is no list.