[Tutor] improving the speed of prime number code

[Kent Johnson]

On Fri, Feb 6, 2009 at 4:19 PM, H.G. le Roy <hgleroy at gmail.com> wrote:

> A part of my code deals with the calculation of prime numbers. However it is
> really slow. Hopefully you have some ideas how to make it faster.
>
> pz = [2]
> # only iterate over odd numbers
> for i in xrange(3,2000000,2):
>   remprod = 1  # product of remainders

Not sure why you accumulate the products, just keep a flag or use an
else clause on the for loop.

>   for j in xrange(len(pz)):
for p in pz:
>     remprod *= (i % pz[j])
>     if remprod == 0:  # if a number is divisible wo remainder its not prime
>       break
>   if remprod > 0:
>     pz.append(i)

You inner loop could be (not tested)
for p in pz:
  if i % p == 0:
    break
else:
  pz.append(i)

You might search the archives for more ideas, this is a popular
question. There is a very slick Python implementation of the Sieve of
Eratosthenes that uses slice assignment to mark off the non-primes.

Kent