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
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
