Lösung für Euler Projekt Aufgabe 5: Warum funktioniert es?

Question

Nach einigem Ausprobieren habe ich eine Lösung gefunden, die sehr schnell für die Project Euler Problem 5 funktioniert. (Ich habe einen anderen Weg gefunden, die korrekt den Beispielfall gelöst (Zahlen 1-10), sondern nahm eine Ewigkeit das eigentliche Problem zu lösen.) Hier geht es:

def test(n): 
    for x in range(2,21): 
     if n % x != 0: 
      return False 
    return True 

def thwart(n): 
    for x in range(2,21): 
     if test(n/x): 
      n /= x 
      return n 
    raise TypeError 

num = 1 
for x in range(1,21): 
    num *= x 

while True: 
    try: 
     num = thwart(num) 
    except TypeError: 
     break 


print(num) 

Mein Hauptproblem zu verstehen, warum thwart(num) wiederholt Aufruf wird genug, um zu der richtigen Lösung zu führen. (D.h. warum ist es in der Lage, die KLEINSTE Nummer zu finden und spuckt nicht irgendeine Zahl aus, die durch die Zahlen 1-20 teilbar ist?) Ich hatte nur einige vage Gedanken bei der Programmierung und war überrascht, wie schnell es funktionierte. Aber jetzt habe ich Probleme herauszufinden, warum es genau funktioniert ... Die optimierten Lösungen anderer Leute auf SO, die ich bis jetzt gefunden habe, sprachen alle über Primfaktoren, die ich nicht sehen kann, wie das zu meinem Programm passen würde ...? Jede Hilfe wird geschätzt! Vielen Dank!

Answer 1

Nun, das ist nicht wirklich ein Coding-Problem, sondern ein mathematisches Problem. Wenn Sie alle Zahlen von 1-20 als die wichtigsten betrachten, erhalten Sie folgendes: 1, 2,3,2^2,5,2^3,7,2^3 .... 2^2 * 5. Der interessante Teil hier ist, dass, sobald Sie mit dem höchsten Exponenten jedes einzelnen Faktors in diesen Zahlen multiplizieren Sie eine Zahl erhalten, die durch jede der Zahlen zwischen eins und zwanzig geteilt werden kann. Sobald Sie erkennen, dass das Problem eine einfache mathematische ist und nähern sie als solche können Sie diesen grundlegenden Code verwenden:

import math 
primes = [2] 
for n in range(3,21): #get primes between 1 and 20 
    for i in primes: 
     if n in primes: 
      break 
     if n%i == 0: 
      break 
     if i> math.sqrt(n): 
      primes.append(n) 
      break 
s = 1 
for i in primes: 
    for j in range(10): # no reason for 10, could as well be 5 because 2^5 >20 
     if i**j > 20: 
      s = s*(i**(j-1)) 
      break 

print s 

Zusätzlich ist der Hinweis, dass die Zahl 2520 die kleinste Zahl ist, die von allen Zahlen geteilt werden kann machen Sie sollten verstehen, wie 2520 gewählt wird: ich ein Foto für Sie getroffen haben: wie Sie caculate können, wenn Sie die größten Exponenten nehmen und multiplizieren sie die Anzahl erhalten 2520.

Was ist Ihre Lösung tut Ihre Lösung nimmt grundsätzlich die Zahl 1 * 2 * 3 * 4 .. * 20 und versucht diese durch jede Zahl zwischen 2 und 20 so zu teilen, dass sie weiterhin relevant bleibt. Indem Sie es über und über laufen lassen, entfernen Sie die nicht benötigten Nummern daraus. früh wird es alle unnötigen 2 entfernen, indem es durch 2 dividiert, die Zahl zurückgibt und dann erneut aufgerufen und wieder durch 2 geteilt wird. Sobald alle zwei eliminiert wurden, werden alle drei eliminiert, sobald alle unnötigen drei eliminiert sind, wird es versuchen, durch 4 zu teilen, und es wird sehen, dass es nicht funktioniert, weiter zu 5, 6, 7 ... und wenn es endet Die Schleife, ohne sie teilen zu können, löst einen TypeError aus und Sie beenden Ihr Programm mit der richtigen Nummer. Dies ist kein effizienter Weg, um dieses Problem zu lösen, aber es wird mit kleinen Zahlen funktionieren.