Style
In Python, there is usual style guide called PEP8 : I think you should follow it to make your code more consistent with all the Python code out in the wild out there. If you want to, you'll find various tools to help you check your Python code : pep8, pycheck, pylint, pyflakes.
Global variables
The fact that you are using a global variable is a good hint that your are probably doing something wrong. It makes your code harder to track but also harder to test and to benchmark.
Also, your should be moving your code which actually performs computations behing an if __name__ == "__main__": : this allows one to easily find where stuff are triggered in your code but also and more importantly to be able to re-use your code by importing your project without re-launching all the computations you might not care about while solving a different project euler problem.
At this point, your code looks like :
import math
def is_prime(n, dict_primes):
if n in dict_primes:
return dict_primes[n]
for num in range(2, math.floor(math.sqrt(n)+1)):
if n % num == 0:
dict_primes[n] = False
return False
dict_primes[n] = True
return True
def main():
"""Main function"""
print("Hello, world!")
count = 0
dict_primes = {}
for num in range (2, 1000000):
q = False
num = str(num)
for i in range(len(num)):
if is_prime(int(num[i:]+num[:i]), dict_primes):
q = True
else:
q = False
break
if q:
count += 1
print (count)
if __name__ == "__main__":
main()
Optimisations : different algorithm
You are using some kind of cache to remember the different numbers you've checked and this is a good idea. Also, you are using a quite efficient way to check if a single number is prime, stopping at sqrt(n) + 1.
However, the best way to do this would probably be to implement a Sieve of Eratosthenes : we build it once and for all and we don't need to compute things later on. This is especially convenient here because we know that we will not need to check for any number bigger than one million.
This is already much faster :
import math
def sieve(limit):
primes = [True] * limit
primes[0] = primes[1] = False
for i in range(2, math.floor(math.sqrt(limit))):
if primes[i]:
for j in range(i*i, limit, i):
primes[j] = False
return primes
def main():
"""Main function"""
print("Hello, world!")
limit = 1000000
count = 0
primes = sieve(limit)
for num in range (2, limit):
q = False
num = str(num)
for i in range(len(num)):
if primes[int(num[i:]+num[:i])]:
q = True
else:
q = False
break
if q:
count += 1
print (count)
if __name__ == "__main__":
main()
Details
At the moment, you are using q to store whether all permutations of num where prime numbers so far. It might be interesting to point out that in Python, you can add an else to loops signifying that that was no break in the loop. Thus, you could write something like :
for i in range(len(num)):
if not primes[int(num[i:]+num[:i])]:
break
else:
count += 1
Alternatively, you could use the all function to write it in a clean and concise way :
if all(primes[int(num[i:]+num[:i])] for i in range(len(num))):
count += 1
Another optimisation
I haven't checked that this really makes the code faster but let's assume that 193939 and all its permutations are prime. Instead of checking all permutations for each permuation and adding one each time every thing is fine, we could only check that we are considering the smallest permutation and add the number of permutations directly. This would look like :
perm = {int(num_s[i:]+num_s[:i]) for i in range(len(num_s))}
if all(n >= num and primes[n] for n in perm):
count += len(perm)
(Please note that I have used a set as I don't want 11 for instance to be counted multiple times just because it is its own permutation).
Another optimisation
If all permutations are supposed to be primes : we know that the first itself must be prime : we can get rid of even numbers : for num in range(3, limit, 2): (you have to initialise count with 1 to count 2).
Also, we know that no even numbers must be in the string : you can add : odd_numbers = {1, 3, 5, 7, 9} out of the loops and if {int(n) for n in num_s}.issubset(odd_numbers): in the loop.
Similarly, 5 can be excluded from the list of allowed numbers as anything ending with 5 with be a multiple of 5 : you can change odd_numbers for final_numbers = {1, 3, 7, 9} and start counting from 2.
Again, this is not benchmarked but you can give it a try if you want.
And now for something different
Instead of going through all numbers and checking conditions that will most of the time not be true, you can use the fact that you already know that for numbers bigger than 9, only {1, 3, 7, 9} are allowed. Thus, you could try to go through the carthesian product of theses numbers using itertool.product.
When considering numbers with n digits, you'll only consider 4**n numbers instead of 10**n (when n = 6 for instance, it makes the difference between 4096 and 100000).
Once this is done, you can even afford to check for much bigger numbers :
def main():
"""Main function"""
print("Hello, world!")
count = 4
nb_digits = 8
primes = sieve(10**nb_digits)
final_numbers = {'1', '3', '7', '9'}
for l in range(2, nb_digits+1):
for p in itertools.product(final_numbers, repeat=l):
p_int = int(''.join(p))
perm = {int(''.join(p[i:]+p[:i])) for i in range(len(p))}
if p_int == min(perm) and all(primes[n] for n in perm):
print(p, len(perm))
count += len(perm)
print (count)
This code checks for numbers of 8 digits by doing 13939 prime checks. Thus, it is not worth using the Eratosthene sieves anymore.
Using your initial code with no cache, we can achieve great performances :
def is_prime(n):
for num in range(2,math.floor(math.sqrt(n)+1)):
if n%num == 0:
return False
return True
def main():
"""Main function"""
print("Hello, world!")
count = 4
nb_digits = 9
final_numbers = {'1', '3', '7', '9'}
for l in range(2, nb_digits+1):
for p in itertools.product(final_numbers, repeat=l):
p_int = int(''.join(p))
perm = {int(''.join(p[i:]+p[:i])) for i in range(len(p))}
if p_int == min(perm) and all(is_prime(n) for n in perm):
print(p, len(perm))
count += len(perm)
print (count)
