Primzahlen sind das Thema des Projecteuler-Problems Nummer 10. Nach dem 3. und 7. Problem befasst sich nun auch das 10. Problem mit den beliebten Zahlen, die durch beinahe nichts teilbar sind. In diesem Artikel wird, wie gewohnt, das Problem eingegrenzt und mit Python gelöst.
Problemvorstellung
Wer die Probleme 3 und 7 bereits gelöst hat, wird mit dem 10. Projecteuler-Problem keine Mühe haben. Wieder geht es um Primzahlen und wieder kann der Sieb des Eratosthenes verwendet werden, um die Lösung zu finden.
Ins Deutsche übersetzt lautet die Aufgabenstellung:
Finde die Summe aller Primzahlen, die kleiner als zwei Millionen sind.
Mit dem Hintergrundwissen aus den bereits gelösten Problemen, bräuchte ich eigentlich keinen zusätzlichen Artikel mehr zu verfassen. Es sind bereits alle Mittel, die hierzu benötigt werden, bereits vorgestellt und mit Erfolg verwendet worden.
Aus diesem Grund lässt es sich nicht wirklich nachvollziehen, warum zum heutigen Zeitpunkt lediglich 47699 der insgesamt 114874 Projecteuler-Teilnehmer eine richtige Lösung zu diesem Problem einreichen konnten. Wahrscheinlich sind sie zeitlich verhindert gewesen 
!
Problemeingrenzung
Obwohl alle Tipps und Tricks zur vollständigen und erfolgreichen Lösung des Problems bereits im Rahmen dieser Artikelserie genannt und beschrieben wurden, möchte ich einige Tatsachen dennoch der Vollständigkeit wegen wiederholen.
In erster Linie ist das wichtiges Werkzeug, welches bei bisher allen Problemen mit Primzahlen bei mir zum Einsatz kam und es auch diesmal tut das Siebes von Eratosthenes. Hierbei handelt es sich um eine Methode, mit welcher man alle Primzahlen bis zu einer gegebenen Zahl N relativ effizient finden kann.
Das Sieb des Eratosthenes
Die Vorgehensweise beim Sieben ist recht simpel und schnell erklärt, dabei geht man am besten grafisch vor: Um alle Zahlen bis N mit dem Sieb zu finden, schreibt man die Zahlen, bildlich gesprochen, alle auf. Dann fängt man mit der ersten bekannten Primzahl, also der 2, an und streicht alle Vielfachen dieser Zahl wieder aus der Liste. Hat man das erledigt, so geht es mit der nächsten nicht gestrichenen Zahl weiter, die nun eine Primzahl sein sollte.
Wenn nichts schief gegangen ist, so bleiben am Ende alle Primzahlen bis N übrig.
Um einige Rechenoperationen, Vergleiche und Abfragen zu sparen, kann die Methode etwas verfeinert werden. Zum einen ist es bekannt, dass es keine geraden Primzahlen gibt. Also können diese sofort aus der Betrachtung ausgeschlossen werden. Zum anderen ist während des Siebens ebenfalls bekannt, dass alle Vielfachen der Primzahl 5 bereits gestrichen sind, wenn die Primzahl 11 an der Reihe ist. Das gilt auch für alle Primzahlen zwischen 5 und 11. Somit kann die nächste zu streichende Vielfache frühstens 11*11 sein.
Aus der zuletzt angestellten Betrachtung folgt sogleich, dass die größte zu prüfende Primzahl maximal die Wurzel aus N sein kann.
x*x <= N
Werden die Verfeinerungen im Code angewendet, erhält man einen relativ effizienten Sieb, der mit den vorgegebenen zwei Millionen mühelos fertig werden sollte.
Problemlösung
Wie versprochen, brauchen wir zur Lösung des zehnten Projecteuler-Problem nur den Sieb des Eratosthenes und eine Summe aller gefundenen Primzahlen, das war es schon!
Im folgenden die kompakte Lösung:
import time as t
import numpy as np
def eratosthenes_vect(N):
primes = np.arange(3,N+1,2) # only uneven figures
primes = np.insert(primes,0,2,0) # ... and two
nUneven = np.size(primes) - 1.0
for i in np.arange(3,np.ceil(np.sqrt(N))+2,2):
primes[(i*i+1)/2-1:nUneven+1.0:i] = 0;
return np.trim_zeros(np.sort(primes))
def solver(N):
Primes = eratosthenes_vect(N)
erg = 0;
for i in Primes:
erg = erg + i
return erg
N = 2000000
t0 = t.clock()
Prim = solver(N)
tn = t.clock() - t0
print("Benoetigte Zeit: %15.6f" %tn)
print("Gefundene Summe: %i" %Prim)
Die Ausgabe des Codes zeigt die benötigt Zeit und die gesuchte Summe:
Benoetigte Zeit: 5.940000
Gefundene Summe: 142913828922
Sechs Sekunden Rechenzeit für alle Primzahlen, die kleiner als zwei Millionen sind, und die Summe daraus ist, denke ich, annehmbar.
Schlusswort
Nach einer etwas langwierigen Zeit, während der nur wenige Artikel in der Serie "Lösungen zu Projecteuler-Problemen mit Python" erschienen sind, gleich zwei Lösungen nach einander. Das ist schon ein Wort und sollte eigentlich mit einem dritten Artikel zum 11. Problem gefeiert werden. Vielleicht lasse ich mich dazu hinreißen 
!
Artikel aus der selben Kategorie:
Meinungsfreiheit für alle!
Es gibt noch keine Kommentare zu “Projecteuler: Lösung zu Problem 10”.
Jede Meinung ist willkommen!