Project Euler: primes in Python

Question

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]

• Mischa Arefiev: It is a good idea to always follow PEP-0008 style guidolines: python.org/dev/peps/pep-0008
• Gareth Rees: See this answer.

Answer 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.

• Jack J: 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"?
• Winston Ewert: @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: @JackJ, store it in a variable.
• Jack J: 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?

Answer 2

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.