Project Euler: primes in Python

Posted on

Problem

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]
``````

Solution

``````# 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.

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.