010 – Primzahlen unter 2 Millionen

 

Die Summe aller Primzahlen unter 10 ist 2+3+5+7 = 17.

Finde die Summe aller Primzahlen unter zwei Millionen!

Lösung

Möglichkeit 1

Wir können den primitiven Ansatz aus Aufgabe 5 benutzen:

grenze = 2000000;
primVec = 2;

for prim = 3 : 2 : grenze
    wurzel = floor(sqrt(prim));
    istPrim = 1;
    for teiler = 3 : 2 : wurzel
        if mod(prim, teiler) == 0
            istPrim = 0;
        end
    end
    if istPrim == 1
        primVec = [primVec prim];
    end
end
primVec;

summe = sum(primVec)

Ergebnis: 142913828922
Rechenzeit: 89.050160 Sekunden.

Möglichkeit 2

Der Algorithmus oben ist sehr langsam. Für große Grenzen kommen wir damit nicht weit, da bei der gegebenen Grenze bereits 100 Millionen Divisionen durchgeführt werden müssen. Wie können wir das verbessern?

Abgesehen von ein paar ziemlich komplexen modernen Ansätzen ist der beste Weg das Sieb des Erastosthenes. Die Idee hinter diesem Algorithmus ist, nicht nach Teilern t von n zu suchen, sondern Vielfache von t aus der Liste der Primzahlen zu löschen.

Prinzipieller Aufbau des Algorithmus:

  1. erstelle eine Liste mit allen Zahlen von 2 bis N
  2. finde die nächste Zahl p, die nicht ausgeschlossen wurde. Dies ist eine Primzahl. Ist sie größer als die Wurzel aus N, gehe zu 5
  3. Markiere alle Vielfachen von p als “keine Primzahl”
  4. gehe zu 2
  5. Die Zahlen, die nicht als “keine Primzahl” markiert wurden, sind die Primzahlen unter N

In Matlab:

grenze = 2000000;
wurzel = sqrt(grenze);

sieb = zeros(1, grenze);
for n = 4 : 2 : grenze
    sieb(n) = 1; % markiere gerade Zahlen über 2
end
for n = 3 : 2 : wurzel
    if sieb(n) == 0  % n ist nicht markiert, also Primzahl
        for m = n * n : 2 * n : grenze
            sieb(m) = 1;
        end
    end
end

summe = 2;
for m = 3 : 2 : grenze
    if sieb(m) == 0
        summe = summe + m;
    end
end

summe

Rechenzeit: 0.130753 Sekunden, also um den Faktor 754 besser!

Wenn wir die geraden Zahlen gar nicht erst in den Vektor aufgenommen hätten, hätten wir die Hälfte des Speicherplatzes und noch ein bisschen Rechenzeit gespart. Diese Verbesserung ist aber mit unübersichtlichen Indexverschiebungen verbunden, daher soll sie hier nur am Rande erwähnt werden.

Ähnliche Artikel

Kommentar verfassen