[Tutor] Help Optimise Code

[=?utf-8?Q?J=F6rg_W=F6lke?=]

* Richard Lovely <roadierich at googlemail.com> [081123 11:35]:
> I've tried a the sieve of erath-whatever as in test_generator,
> implemented using itertools functions, but it hit max recusion depth
> somewhere before 1000 primes, and I'm after millions of primes.

I found an old implementation for some exercise of the 
"sieve of Eratosthenes" in my backups and its not recursive but 
iterative:

#!/usr/bin/env python

l=10000*[1]
for i in range(2,len(l)):
    if l[i] == 1:
       print i
           for j in range(i+1,len(l)):
               if j%i == 0:
                   l[j]=0

Yes, it is pretty slow for a range of a million, but it speeds up 
a little after half an hour or so :-)
You might want to have a look at the bsd-games package, which
includes a program named primes. It prints out primes at a 
reasonable speed - up to 4294967295 (the default). The manpage says:
"
BUGS
     primes won't get you a world record.
"
If you can get it to work faster in python? I doubt that.
primes uses IIRC atkin-sieve: "http://cr.yp.to/papers/primesieves.pdf"

-- 
You have an ambitious nature and may make a name for yourself.