Euler 35 - python solution taking too long

Question

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

Ned Batchelder · Answer 1 · 2012-01-27 20:27:00Z

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.

dan04 · Answer 2 · 2012-01-27 20:30:08Z

up vote 2 down vote

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.

answered Jan 27 '12 at 20:30

dan04
1212

1

Your total would be off by 1: you would miss 2! But good point! – Ned Batchelder Jan 27 '12 at 20:33

1

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. – g.d.d.c Jan 27 '12 at 20:34

add comment (requires an account with 50 reputation)

asked	1 year ago
viewed	293 times
active	1 year ago

Euler 35 - python solution taking too long

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

2 Answers

Your Answer

Community Bulletin

Linked

Euler 35 - python solution taking too long

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

2 Answers

Your Answer

Sign up or login

Post as a guest

Community Bulletin

Linked

Related