Project Euler Nr. 5

Bei Problem Nr. 5 soll die kleinste positive Zahl gefunden werden, die ganzzahlig durch alle Zahlen von 1 bis 20 teilbar ist. Das Problem hatte ich vor einiger Zeit bereits gelöst. Mich interessieren hier einmal verschiedene Lösungen, um zu sehen, wie performant sie jeweils sind und wie weit ich den Quellcode optimieren kann.

Kategorie Brute-Force

Eine gangbare, aber nicht sehr performante Lösung ab n = 19.

def loesung_ermitteln(n):
    # Funktion, die nach einer Loesung fuer das
    # Problem Nr. 5 sucht: Kleinste Zahl, die durch
    # alle Zahlen von 1 bis 20 teilbar ist.
    zahl = n

    while True:
    
        for i in range(1,n+1):

            if zahl % i != 0:
                # print("Nächste Zahl",i)
                break

        if i == n:
            return zahl
        else:
            zahl += n


print("Arbeit an Problem Nr. 5")

# Ergebnis: 2520
print("10")
print(">>>",loesung_ermitteln(10))

input("Weiter?")

# Ergebnis: 9-stellige Zahl
print("20")
print(">>>",loesung_ermitteln(20)) 

Die einzige Optimierung ist, dass jeweils die zu prüfende Zahl um sich selbst erhöht wird. Eine Zahl die durch 10 teilbar sein soll, kann nur ein Vielfaches von 10 sein, also 10, 20, 30, 40, 50 usw.

Ich habe die Funktion unverändert gelassen, aber den Code im „Hauptprogramm“ angepasst:

print("Arbeit an Problem Nr. 5".center(40," "))

print("Zahl","Kleinstes gemeinsames Vielfaches",sep="\t")
print(40 * "=")

for zahl in range(1,21):
    print("{:>4}\t{:>32}".format(zahl,loesung_ermitteln(zahl)))

Das ergibt dann in der Konsole:

        Arbeit an Problem Nr. 5         
Zahl Kleinstes gemeinsames Vielfaches
========================================
   1                                1
   2                                2
   3                                6
   4                               12
   5                               60
   6                               60
   7                              420
   8                              840
   9                             2520
  10                             2520
  11                            27720
  12                            27720
  13                           360360
  14                           360360
  15                           360360
  16                           720720
  17                         12252240
  18                         12252240
  19                        232792560
  20                        232792560

Kategorie Mathematik soll helfen

Letztlich wird das kleinste gemeinsame Vielfache (kgV) der Zahlen 1 bis n gesucht. Für die Zahlen von 1 bis 10 ist das 2520. Die Mathematik müsste folglich helfen können. Wenn ich es richtig sehe, dann müsste ich hier mehrere Aufgaben bewältigen:

1. Primzahlen im Bereich 1 bis 20 bestimmen
2. Primfaktorzerlegung (Integer factorization) für die Zahlen 1 bis 20 leisten
3. Mathematisch mit (1) und (2) das kleinste gemeinsame Vielfache ermitteln.

Ich spiele die Primfaktorzerlegung manuell für den Zahlenraum 1 bis 20 durch:

Zahl	Primfaktor	Zahl	Primfaktor
1	1	11	Primzahl
2	Primzahl	12	2 ** 2 * 3
3	Primzahl	13	Primzahl
4	2 ** 2	14	2 * 7
5	Primzahl	15	3 * 5
6	2 * 3	16	2 ** 4
7	Primzahl	17	Primzahl
8	2 ** 3	18	2 * 3 ** 2
9	3 ** 2	19	Primzahl
10	2 * 5	20	2 ** 2 * 5

Wenn ich der Wikipedia folge, dann nimmt man für das kgV „alle Primfaktoren, die in irgendeiner der Zahlen vorkommen, mit der jeweils höchsten vorkommenden Potenz“. Daraus würde sich hier in diesem Fall ergeben:

kgV(1...20) = 1 * 2 ** 4 * 3 ** 2 * 5 * 7 * 11 * 13 * 17 * 19 = 232792560

Also: Das dürfte in der Umsetzung performanter sein. Die Primzahlen für den benötigten Bereich könnte man einem Skript beigeben, so dass hier nicht erst gesiebt werden muss. Die Primfaktorzerlegung performant zu implementieren (mögliche Algorithmen) dürfte anspruchsvoll sein und in geeigneter Form die Terme auszuwerten, ist erst einmal eine Herausforderung.