197 wird als zyklische Primzahl bezeichnet, da die durch Drehen der Ziffern erhaltenen Zahlen 197, 971, 719 alle Primzahlen sind.
Weniger als 100 hat 13 zyklische Primzahlen: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79 und 97.
Wie viele reisende Primzahlen sind weniger als 1 Million? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2035
0,2,4,5,6,8 sind nicht in den Ziffern von zyklischen Primzahlen mit zwei oder mehr Ziffern enthalten. Dies liegt daran, dass diese Zahlen in der ersten Ziffer immer durch 2 oder 5 teilbar sind. Daher sollten wir außer 2,5 Zahlen berücksichtigen, die nur 1,3,7,9 enthalten. Um diese Anzahl von Sätzen zu erstellen, habe ich eine Funktion namens mapall erstellt. mapall ist eine Funktion, die jedes Element e1 und e2 einer bestimmten Menge iter1 für die Häufigkeit kombiniert, mit der num durch eine geeignete Kopplungsregel f angegeben wird, und das Ergebnis als Mengenart zurückgibt. Zuerst habe ich mit ['', 1,3,7,9] als iter1 eine 6-stellige Zahl erstellt, die als die größte angesehen wird. '' Ist enthalten, damit die Elemente der ursprünglichen Liste in der kombinierten Liste verbleiben, wenn sie kombiniert werden. Zum Beispiel wird '' + '3' zu '3' und die Elemente der ursprünglichen Liste bleiben in der kombinierten Liste.
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