[PYTHON] Qu'est-ce que Project Euler 3 Acceleration?

Les facteurs premiers de 13195 sont 5, 7, 13, 29.

Trouvez le plus grand des facteurs premiers de 600851475143. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203

J'ai essayé de le résoudre au fur et à mesure que je l'avais imaginé.

target = 600851475143
i = 1
while target != 1:
  i += 2
  while not target % i:
    target /= i
print i

Ceci est une réponse en supposant que 600851475143 est un nombre composé. L'instruction while n'est pas tellement répétée car c'est un nombre composé. Par conséquent, il n'y a aucun problème avec ce code. Cependant, si 600851475143 est un nombre premier, ce code aura des problèmes. 600851475143/2 Le surplus sera calculé environ 3 trillions de fois.

En d'autres termes, les situations suivantes se produiront.

Dans la fourniture de services, ce n'est pas un problème à un stade précoce, et cela a tendance à être un problème tardivement. De ce point de vue, même s'il s'agit d'un nombre premier, le code suivant qui permet d'éviter la lenteur du point de vue de la couverture des risques peut être préférable. Dans le code suivant, une liste de nombres premiers est créée jusqu'à la racine carrée de la cible à l'aide du tamis Elatostines, et la factorisation des nombres premiers est tentée sur la base de la liste. Il semble qu'une vitesse de traitement stable puisse être obtenue en ce que le calcul du reste n'est pas effectué pour tous les nombres premiers et que le calcul n'est effectué que jusqu'à la racine carrée de la cible. (Bien que le code ci-dessus ne puisse calculer que jusqu'à la racine carrée de la cible.)

import mymath
import math
target = 600851475143
pri = mymath.get_primes(int(math.sqrt(target)))
max_p = 1
for p in pri['list']:
    while not target % p:
        target /= p
        max_p = p
if target != 1:
    print target
else:
    print max_p

Cliquez ici pour mymath. http://www.sato-pat.co.jp/