[Tutor] improving the speed of prime number code

[taserian]

One potential way to speed up is not to divide by every prime in your pz
list, but only up to the square root of i.

For example, to test if 37 is prime, you would only need to look at primes
less than or equal to int(sqrt(37)) = 6.08. . .

Tony R.

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

> Hi,
>
> I'm stuck with Problem 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)
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20090206/1e857866/attachment.htm>