6
\$\begingroup\$

Here is my solution for Project Euler 35. (Find the number of circular primes below 1,000,000. Circular meaning all rotations of the digits are prime, i.e. 197, 719, 971.) The code takes about 30 minutes to run. Can you help me identify which parts of the algorithm are hogging up computation time?

I know there are many solutions out there, I just want to know why this one is soooo slow. I suspect it has something to do with the p.count function call.

  • p is initialized to a list of all primes below 1 million using the Sieve of Eratosthenes.
  • total is initialized to 0.
for i in p:
    primer = str(i)
    circ = 1
    for j in range(len(primer)-1):
        primer = primer[1:]+primer[:1]
        if (p.count(int(primer)) == 1):
            circ += 1
    if circ == len(primer):
        total += 1
\$\endgroup\$

migrated from stackoverflow.com Jan 27 '12 at 21:30

This question came from our site for professional and enthusiast programmers.

7
\$\begingroup\$

Your p is a list. Then you do p.count(x) to see if x is a prime. This does a linear search of the list, and in fact, has to examine every element of p, not just those up to the occurrence of x. Instead, change p to a set. It will run much faster. Also, once you see that a rotation is not prime, you can stop checking all the rotations.

\$\endgroup\$
3
\$\begingroup\$

All primes below a million? You only need the ones that consist of the digits 1, 3, 7, or 9.

Edit: And the single-digit circular primes 2 and 5.

\$\endgroup\$
  • 1
    \$\begingroup\$ Your total would be off by 1: you would miss 2! But good point! \$\endgroup\$ – Ned Batchelder Jan 27 '12 at 20:33
  • 1
    \$\begingroup\$ While accurate if he were only concerned with primes > 10, this optimization would actually produce the wrong answer because 5 counts as a circular prime according to the problem description. It's a good idea if you special case 5 though. \$\endgroup\$ – g.d.d.c Jan 27 '12 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy