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. 001.png

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

002.png

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

Recommended Posts

Qu'est-ce que Project Euler 3 Acceleration?
Project Euler 2 Acceleration 2.21 Économisez des microsecondes.
Projet Euler 37
Projet Euler 47
Projet Euler 31
Projet Euler 4
Projet Euler 38
Projet Euler 26
Projet Euler 8
Projet Euler 22
Projet Euler 19
Projet Euler 50
Projet Euler 33
Projet Euler 32
Projet Euler 43
Projet Euler 35
Projet Euler 36
Projet Euler 24
Projet Euler 48
Projet Euler 45
Projet Euler 6
Projet Euler 44
Projet Euler 39
Projet Euler 40
Projet Euler 49
Projet Euler 29
Projet Euler 27
Projet Euler 41
Projet Euler 18
Projet Euler 13
Projet Euler 30
Projet Euler 16
Projet Euler 14
Projet Euler 34
Projet Euler 25
Qu'est-ce que l'espace de noms
Qu'est-ce que copy.copy ()
Qu'est-ce que dotenv?
Qu'est-ce que Linux
Qu'est-ce que le klass?
Qu'est-ce que SALOME?
Qu'est-ce que Linux?
Qu'est-ce que Linux
Qu'est-ce que pyvenv
Qu'est-ce que __call__
Qu'est-ce que Linux
Qu'est-ce que Python
Qu'est-ce qu'une distribution?
Qu'est-ce que le F-Score de Piotroski?
Qu'est-ce que Raspberry Pi?
[Python] Qu'est-ce que Pipeline ...
Qu'est-ce que Calmar Ratio?
Qu'est-ce qu'un terminal?
[Tutoriel PyTorch ①] Qu'est-ce que PyTorch?
Qu'est-ce qu'un hacker?
Qu'est-ce que JSON? .. [Remarque]
À quoi sert Linux?
Qu'est-ce qu'un pointeur?
Qu'est-ce que l'apprentissage d'ensemble?
Qu'est-ce que TCP / IP?
Qu'est-ce que __init__.py de Python?