197 is called a cyclic prime number, because the numbers 197, 971, 719 obtained by rotating the digits are all prime numbers.
Less than 100 have 13 cyclic primes: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many traveling primes are less than 1 million? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2035
0,2,4,5,6,8 are not included in the digits of cyclic prime numbers with two or more digits. This is because every time these numbers are in the first digit, they are divisible by 2 or 5. Therefore, other than 2,5, we should consider numbers that include only 1,3,7,9. In order to create this number of sets, I created a function called mapall. mapall is a function that combines each element e1 and e2 of a set iter1 for the number of times num specified by an appropriate associative law f and returns the result as a set type. First, using ['', 1,3,7,9] as iter1, I made a 6-digit number that is considered to be the largest. '' Is included so that when combined, the elements of the original list will remain in the combined list. For example,'' + '3' becomes '3', and the elements of the original list will remain in the combined list.
import mymath
def circle(num):
s = str(num)
for c in range(len(s)):
s = s[1:]+s[0]
yield int(s)
def mapall(f, iter1, num=1):
ret = iter1
for i in range(num):
ret = set([f(e1,e2) for e1 in ret for e2 in iter1])
return ret
def connect_num(e1,e2):
return str(e1)+str(e2)
def main():
pri = mymath.get_primes(10**6)
n_list = ['',1,3,7,9]
pn5 = mapall(connect_num, n_list,5)
pn5.remove('')
ans = {}
for pn in pn5:
if pn in ans:
continue
flag = True
for n in circle(pn):
if not pri['bool'][n]:
flag = False
break
if flag:
for n in circle(pn):
ans[n] = True
print len(ans)+2
main()
Recommended Posts