# [Tutor] primes

Max Noel maxnoel_fr at yahoo.fr
Fri Mar 18 02:17:24 CET 2005

```On Mar 17, 2005, at 23:54, Danny Yoo wrote:

> Hi Gregor,
>
> Here is one that's traduced... er... adapted from material from the
> classic textbook "Structure and Interpretation of Computer Programs":
> <SNIP>

Ooh, nifty.

Okay, I decided to learn how to use the timeit module, so I used it to
compare my algorithm (which, I just noticed, is a Python implementation
of the Sieve of Erastothenes) to the one Gregor originally posted
(albeit slightly optimized -- the only even prime number is 2, so
there's no need to test them), and a further optimized version of it
(stops looping at sqrt(x)).
While I was at it, I optimized my algorithm further (in both memory
usage and speed): it uses xrange and doesn't bother testing even
numbers.

Now, I did expect my algorithm to be the fastest. What I didn't
expect, though, was for the differences to be *that* massive. Letting
all three functions loose on finding all the prime numbers from 2 to
50000, I got the following results (test machine: G4 867 running Python
2.3 on OS X 10.3.8):

listPrimes: 0.508284091949 seconds			# my algorithm
primeConciseOptimized: 2.18135714531 seconds	# Gregor's, optimized
primeConcise: 399.251116991 seconds			# Gregor's, (partially optimized)

As I suspected, when increasing the range, so do the differences.
listPrimes finds all prime numbers from 2 to 200000 in 2.55 seconds,
primeConciseOptimized in 15.81. At that point I had dropped
primeConcise, as it being O(n^3) as far as I can tell, it would have
taken ages to run. However, I thought the difference between listPrimes
and primeConciseOptimized would increase faster than that. So
primeConciseOptimized seems like the best compromise between speed and
conciseness.

Here's the (final?) version of the script I used:

#!/usr/bin/env python

import math
import timeit

def primeConcise(limit):
return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2]
+ range(3,x,2) if x%y==0]]

def primeConciseOptimized(limit):
return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2]
+ range(3,int(math.sqrt(x)), 2) if x%y==0]]

def isPrime(x, primeList):
limit = int(math.sqrt(x))
for i in primeList:
if x % i == 0:
return False
if i >= limit:
break
return True

def listPrimes(upperLimit):
listOfPrimes = [2]
for i in xrange(3, upperLimit, 2):
if isPrime(i, listOfPrimes):
listOfPrimes.append(i)
return listOfPrimes

if __name__ == '__main__':
t1 = timeit.Timer('listPrimes(50000)', 'from __main__ import
listPrimes')
t2 = timeit.Timer('primeConciseOptimized(50000)', 'from __main__
import primeConciseOptimized')
t3 = timeit.Timer('primeConcise(50000)', 'from __main__ import
primeConcise')
print t1.timeit(1)
print t2.timeit(1)
print t3.timeit(1)

-- Max
maxnoel_fr at yahoo dot fr -- ICQ #85274019
"Look at you hacker... A pathetic creature of meat and bone, panting
and sweating as you run through my corridors... How can you challenge a
perfect, immortal machine?"

```