[Tutor] primes

Max Noel maxnoel_fr at yahoo.fr
Fri Mar 18 00:42:00 CET 2005


On Mar 17, 2005, at 22:28, Gregor Lingl wrote:

> Hi!
> Who knows a more concise or equally concise but more efficient
> expression, which returns the same result as
>
> [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]]
>
> Gregor
>
> P.S.: ... or a more beautiful one ;-)

	Hmm... I don't have "beautiful" or "concise", but I can offer "fast". 
Here goes:

#!/usr/bin/env python

import math

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

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


if __name__ == '__main__':
     import sys
     num = int(sys.argv[-1])
     print listPrimes(num)



	That's the fastest way I can think of -- but I can't prove it, as I 
don't know how to use the timeit module.

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



More information about the Tutor mailing list