[PYTHON] Was ist Project Euler 3-Beschleunigung?

Die Hauptfaktoren von 13195 sind 5, 7, 13, 29.

Finden Sie den größten der Primfaktoren von 600851475143. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203

Ich habe versucht, es zu lösen, als ich darauf kam.

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

Dies ist eine Antwort unter der Annahme, dass 600851475143 eine zusammengesetzte Zahl ist. Die while-Anweisung wird nicht so oft wiederholt, da es sich um eine zusammengesetzte Zahl handelt. Daher gibt es kein Problem mit diesem Code. Wenn jedoch 600851475143 eine Primzahl ist, tritt bei diesem Code ein Problem auf. 600851475143/2 Der Überschuss wird ungefähr 3 Billionen Mal berechnet.

Mit anderen Worten, die folgenden Situationen treten auf.

Bei der Bereitstellung von Diensten ist dies in einem frühen Stadium kein Problem, und es ist in der Regel zu einem späten Zeitpunkt ein Problem. Unter diesem Gesichtspunkt kann, selbst wenn es sich um eine Primzahl handelt, der folgende Code vorzuziehen sein, der die Langsamkeit unter dem Gesichtspunkt der Risikoabsicherung vermeiden kann. Im folgenden Code wird mit dem Elatostines-Sieb eine Liste von Primzahlen bis zur Quadratwurzel des Ziels erstellt, und die Primfaktorisierung wird anhand der Liste versucht. Es scheint, dass eine stabile Verarbeitungsgeschwindigkeit erhalten werden kann, indem die Restberechnung nicht für alle Primzahlen durchgeführt wird und dass die Berechnung nur bis zur Quadratwurzel des Ziels durchgeführt wird. (Obwohl der obige Code nur bis zur Quadratwurzel des Ziels berechnen kann.)

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

Klicken Sie hier für mymath. http://www.sato-pat.co.jp/