Finding circular primes

Question

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))

Answer 1

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\$ instead of \$\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.

• Po Chen Liu: Hi! thanks for your response, I am a newbie and when I solve these puzzles often I know what to do, not how to do it so I simply google the functions. With the rwh_prime function, I dont understand much because I'm not that good of a coder, could you propose an example with your comment?
• Po Chen Liu: Also, when i delete code from 'counter' onwards the code is significantly faster (1 sec) so maybe it's not that?
• jschnei: I'm not saying the reason your code is slow is because of the rwh_primes function, but because of your is_prime function (which you call after counter). Don't use your is_prime function; instead, just check whether the prime is in your list of primes (but make that list a set first).
• Po Chen Liu: Making it a set made my code go from ~30sec to 1.5. Thanks dude!