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  + [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 + thingy) 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))
- I don’t really understand the majority of names. What does
f7mean? What does the
rwh_primesmean? Why is the
lisp? What is the difference between
counter? Having good names is a huge part of good coding practice.
rwh_primescomputes a list of primes, which is good, but you then ignore list of primes when you test for primality in the
is_primemethod (which, since it goes up to N instead of 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
lispwith 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
zto a single index
- 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
f7uniqifies 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.