3797 a une propriété intéressante: d'abord, c'est un nombre premier, et quand les chiffres sont enlevés de gauche à droite, ce sont tous des nombres premiers (3797, 797, 97, 7). De même, les chiffres de droite à gauche. Tous sont des nombres premiers sauf pour (3797, 379, 37, 3).
Il n'y a que 11 nombres premiers qui peuvent être tronqués à partir de la droite ou de la gauche. Trouvez la somme.
Remarque: nous ne considérons pas que 2, 3, 5, 7 sont tronqués. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2037
Ces nombres ont un premier chiffre de 3 ou 7. Si le premier chiffre est 1,4,6,8,9, le nombre lui-même n'est pas un nombre premier, et si le premier chiffre de deux chiffres ou plus est 2,5, c'est un multiple de 2 ou un multiple de 5. De plus, vous n'avez pas besoin de 2,4,5,6,8 dans les chiffres du milieu. En effet, si 2,4,5,6,8 est entré au milieu lorsqu'il est arrondi à partir de la droite, le nombre n'est plus un nombre premier. De plus, il n'y a pas de nombre de 3 chiffres ou plus dont le chiffre maximum est de 2,5. D'après la considération ci-dessus, il est de 1,3,7,9 sauf pour les chiffres, mais si le chiffre le plus significatif est 2 ou 5 et qu'il y a un ou plusieurs 1, 7 au milieu, ce sera toujours un multiple de 3 au milieu. De plus, si le chiffre le plus significatif est 2 ou 5 et le reste est 3 ou 9, il sera un multiple de 3 lorsqu'il est arrondi à partir de la gauche. Pour les nombres à deux chiffres, 23 et 53 sont des nombres premiers qui satisfont à la condition. Pour les nombres autres que ceux-ci, on peut voir que les nombres dans lesquels chaque chiffre se compose de 1,3,5,7 doivent être considérés.
Il se termine lorsque le nombre de colonnes de réponses atteint 11.
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()
J'ai écrit le code que 23,53 demande également. Dans ce cas, le nombre à combiner comprend non seulement 1,3,7,9 mais aussi 2,5. De plus, l'ensemble nr (N est le nombre de répétitions + 1) de nombres à N chiffres de nombres premiers joints par la droite est vide, ou l'ensemble nr (N est) de nombres à N chiffres de nombres premiers joints par la gauche. Il se termine lorsque le nombre de répétitions + 1) devient vide. Ce code a également confirmé que le nombre ci-dessus n'était que de 11.
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