[Tutor] primes

[Max Noel]

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?"