Problem

I’m coding for a project euler question and every now and then, the question will demand a program that is efficient even when doing brute force. Which I struggle with.

Below is a piece of code for problem 35 which I’m fairly certain works correctly so far with numbers under 10000 however when I set it to 1 million it takes way too long to run. I still havent got an answer yet and it’s been running for about 15 mins….

If anyone could give me general tips on efficiency that would be awesome!

```
def rwh_primes(n):
sieve = [True] * n
for i in range(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*int((n-i*i-1)/(2*i)+1)
return [2] + [i for i in range(3,n,2) if sieve[i]]
def is_prime(n):
for i in range(3, n):
if n % i == 0:
return False
return True
def f7(seq):
seen = set()
seen_add = seen.add
return [x for x in seq if not (x in seen or seen_add(x))]
primes = rwh_primes(1000000)
lisp = []
working = []
count = 0
counter = 0
for x in primes:
z = 1
y = (len(str(x)) + 1)
if len(str(x)) == 2:
thingy = list(str(x))
number = int(thingy[1] + thingy[0])
if is_prime(number) == True:
lisp.append(x)
elif len(str(x)) < 2:
lisp.append(x)
else:
while count < len(sorted(str(x))) - 1:
num = list((str(x) + str(x)))
new = num[z:y]
newest = ''.join(new)
verynew = int(newest)
working.append(verynew)
count += 1
z += 1
y += 1
if count == len(sorted(str(x))) - 1:
for a in working:
if is_prime(a) == True:
counter += 1
if counter == len(working):
lisp.append(x)
lisp = f7(lisp)
count = 0
counter = 0
working = []
print(len(lisp))
```

Solution

Some observations:

- I don’t really understand the majority of names. What does
`f7`

mean? What does the`rwh`

in`rwh_primes`

mean? Why is the`lisp`

variable called`lisp`

? What is the difference between`count`

and`counter`

? Having good names is a huge part of good coding practice. - Your
`rwh_primes`

computes a list of primes, which is good, but you then ignore list of primes when you test for primality in the`is_prime`

method (which, since it goes up to N$N$ instead of N−−√$\sqrt{N}$, is particularly slow and probably the cause of most of your troubles). Instead of running`is_prime`

, why not simply check whether`number in primes`

(note that for this, you probably want to make primes a set rather than a list). - I’m not sure why you do
`len(sorted(str(x)))`

instead of just`len(str(x))`

; sorting a list doesn’t change its length. - You don’t need to keep track of which numbers are circular primes, just how many there are. You could replace
`lisp`

with a simple count. - Why do you deal with the length 2 case differently than the case where the length is greater than 2? I understand why you might want to deal with the length 1 case separately, but your code that works for your larger cases should also work for the length 2 case.
- Your method for getting a cyclic shift of the number is interesting (doubling the string then taking a substring), but python makes it really easy to just do
`int(num[i:] + num[:i])`

, which does most of the work of your while loop in one line. You can now also reduce your two indices`y`

and`z`

to a single index`i`

. - Instead of checking whether you’ve appended all cyclic shifts during each repetition of your while loop, why not just finish your while loop and then loop through the cyclic shifts (i.e. move the if statement outside the while loop). You do this again in your inner loop (
`for a in working`

). - It looks like
`f7`

uniqifies a list. While I don’t think you actually need to do any uniqifying here, even if you do want the list of all circular primes (because you add them in increasing order), a much easier way to do this in python is simply`list(set(x))`

; this is fast enough for most purposes.