[Tutor] improving the speed of prime number code

[bob gailer]

H.G. le Roy wrote:
> Hi,
>
> I'm stuck with Problem 10 
> (http://projecteuler.net/index.php?section=problems&id=10 
> <http://projecteuler.net/index.php?section=problems&id=10>) :-)
>
> 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
>   for j in xrange(len(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)
>   
I know prime # algorithms have been discussed on at least one of the 
Python lists, and are also found in various internet resources.

Without consulting them let me offer:
- odd prime numbers are = 6x-1 or 6x+1 where x is integer.
    That reduces the # of candidates.
- the highest candidate you need to test is <= the square root of the 
candidate.
    That reduces cycles of the inner for loop
- there is no need to initialize remprod
- you can use "for j in pz:" to access successive pz's
    in which case you'd write i % j
- there is no need to multiply remprod by the remainders as you don't 
use that result later.

-- 
Bob Gailer
Chapel Hill NC
919-636-4239