3797 hat eine interessante Eigenschaft. Erstens ist es eine Primzahl, und wenn die Ziffern von links nach rechts entfernt werden, sind es alle Primzahlen (3797, 797, 97, 7). Ebenso die Ziffern von rechts nach links. Mit Ausnahme von (3797, 379, 37, 3) sind alle Primzahlen.
Es gibt nur 11 Primzahlen, die von rechts oder von links abgeschnitten werden können. Finden Sie die Summe.
Hinweis: Wir betrachten 2, 3, 5, 7 nicht als abgeschnitten. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2037
Solche Zahlen haben eine erste Ziffer von 3 oder 7. Wenn die erste Ziffer 1,4,6,8,9 ist, ist die Zahl selbst keine Primzahl, und wenn die erste Ziffer mit zwei oder mehr Ziffern 2,5 ist, ist sie ein Vielfaches von 2 oder ein Vielfaches von 5. Außerdem benötigen Sie keine 2,4,5,6,8 im mittleren Bereich. Dies liegt daran, dass die Zahl keine Primzahl mehr ist, wenn 2,4,5,6,8 in der Mitte eingegeben wird, wenn sie von rechts abgerundet wird. Außerdem gibt es keine Nummer mit 3 oder mehr Ziffern, die eine maximale Ziffer von 2,5 hat. Aus der obigen Überlegung ergibt sich mit Ausnahme der Ziffern 1,3,7,9. Wenn jedoch die höchstwertige Ziffer 2 oder 5 ist und sich in der Mitte eine oder mehrere 1, 7 befinden, ist es in der Mitte immer ein Vielfaches von 3. Wenn die höchstwertige Ziffer 2 oder 5 und der Rest 3 oder 9 ist, ist sie ein Vielfaches von 3, wenn sie von links abgerundet wird. Bei zweistelligen Zahlen sind 23 und 53 Primzahlen, die die Bedingung erfüllen. Bei anderen Zahlen als diesen ist ersichtlich, dass die Zahlen, in denen jede Ziffer aus 1,3,5,7 besteht, berücksichtigt werden sollten.
Es endet, wenn die Anzahl der Antwortspalten 11 erreicht.
def conjoin(f, iter1, iter2):
return set(f(e1,e2) for e1 in iter1 for e2 in iter2)
def connect_num(e1,e2):
return str(e1)+str(e2)
def is_prime(num,pri):
num = int(num)
if num < len(pri['bool']):
return pri['bool'][num]
M = (num**0.5)+1
#print num
for p in pri['list']:
if p > M:
return True
if (num % p) == 0:
return False
p = pri['list'][-1]+2
while p<M:
if (num % p) == 0:
return False
p += 2
return True
import mymath
def get_pri(iter1, pri):
ret = []
for n in iter1:
if is_prime(n,pri):
ret.append(n)
return set(ret)
def main():
MAX = 10**7
pri = mymath.get_primes(MAX)
nr = [3,7]
nl = [3,7]
n2 = [1,3,7,9]
s = set(['23', '53'])
MAX_LEN = 11
while len(s)<MAX_LEN:
if len(nr) == 0:
break
nr = set(get_pri(conjoin(connect_num,nr,n2),pri))
nl = set(get_pri(conjoin(connect_num,n2,nl),pri))
s = s | (nr & nl)
ans = 0
for n in s:
ans += int(n)
print s
print ans
main()
Ich habe den Code geschrieben, nach dem 23,53 auch fragt. In diesem Fall umfasst die zu kombinierende Zahl nicht nur 1,3,7,9, sondern auch 2,5. Auch die Menge nr (N ist die Anzahl der Wiederholungen + 1) von N-stelligen Zahlen von Primzahlen, die von rechts verbunden sind, ist leer, oder die Menge nr (N ist) von N-stelligen Zahlen von Primzahlen, die von links verbunden sind. Es endet, wenn die Anzahl der Wiederholungen + 1) leer wird. Dieser Code bestätigte auch, dass die obige Nummer nur 11 war.
import copy
import mymath
def main():
MAX = 10**7
pri = mymath.get_primes(MAX)
nr = set(get_pri(range(1,10),pri))
nl = copy.deepcopy(nr)
ns = [1,2,3,5,7,9]
s = set([])
while len(nr)>0 and len(ns)>0:
nr = set(get_pri(conjoin(connect_num,nr,ns),pri))
nl = set(get_pri(conjoin(connect_num,ns,nl),pri))
s = s | (nr & nl)
ans = 0
for n in s:
ans += int(n)
print s
print ans
Recommended Posts