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\$
1

2 Answers 2

Reset to default
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\$
2
  • 1
    \$\begingroup\$ Your total would be off by 1: you would miss 2! But good point! \$\endgroup\$ Commented Jan 27, 2012 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\$ Commented Jan 27, 2012 at 20:34

You must log in to answer this question.