Startseite Mathematik-Online        Themenliste

Mathematik-Online, Excel-VBA

Das Sieb des Eratosthenes ist ein besonders einfaches Verfahren, um Primzahlen aufzulisten:

Excel-VBA: Primzahlen

Anfrage: Jens Roland, web
Mein folgender VBA-Code berechnet mit dem Siebverfahren von Eratosthenes alle Primzahlen bis zu einer variablen Grenze n:
...
For i = 2 To n
   Cells(i, 1) = i
Next i

For i = 2 To Int(sqr(n))
   For each c in Range(Cells(i+1, 1), Cells(n, 1))
     If cells(i, 1) <> 0 then
       If c mod cells(i, 1) = 0 then
         c.ClearContents
       End If
     End If
   Next c
Next i
...
Das Programm läuft fehlerfrei, aber kann ich evtl. mit mathematischen Tricks die Rechenzeit verkürzen ?

Antwort

Folgende Zeilen vermeiden unnötige Wiederholungen:

'Ausser der 2 nur die ungeraden Zahlen auflisten:
cells(2,1) = 2
For i = 3 To n Step 2
   Cells(i, 1) = i
Next i

'Durchlauf der ungeraden Zahlen von 3 bis Ganzzahl(Wurzel(n)):
For i = 3 To Int(Sqr(n)) Step 2
  If Cells(i, 1) > 0 Then

'Von i^2 bis n alle ungeraden Vielfachen k der Zahl i löschen:
    For k = i ^ 2 To n Step 2 * i
      If Cells(k, 1) > 0 Then
        Cells(k, 1).ClearContents
      End If
    Next k

  End If
Next i


Mathematik-Online, Excel-VBA,   Primzahlen

Bemerkung

Das Siebverfahren ist nach dem griechischen Mathematiker Eratosthenes (276 bis 196 v. Chr.) benannt - der übrigens als erster den Umfang der Erde ziemlich genau berechnet hat. Um alle Primzahlen ≤ n zu bestimmen, schreibt man zuerst alle Zahlen von 2 bis n auf, streicht dann ausser der 2 alle geraden Zahlen und fährt so fort mit den Zahlen, die durch 3 teilbar sind. Dann streicht man alle Zahlen, die durch 5 teilbar sind usw. Dieses Verfahren lässt sich problemlos modifizieren, so dass man die meisten Wiederholungen vermeiden kann. Für n = 70 zeigen wir nun, wie unser obiger Programmcode funktioniert:

Wir wollen also alle Primzahlen ≤ 70 auflisten und erzeugen zuerst die Zahlenreihe 2, 3, 5, 7, 9, 11, ... , 69. Aus dieser Reihe streichen wir ab 3² alle ungeraden Vielfachen der Zahl i = 3, also 9, 15, 21, ... 63, 69. Dann löschen wir 25, 35, 45, 55, 65, also alle ungeraden Vielfachen der Zahl i = 5, wobei wir erst bei i² = 5² beginnen, weil 3·5 bereits im vorherigen Schritt gelöscht wurde. Schließlich müssen wir nur noch die restlichen ungeraden Vielfachen 7² und 9·7 der Zahl i = 7 löschen.

Damit enthält unserer Liste nun keine Vielfachen mehr der Zahlen zwischen 2 und 70. Angenommen, es gäbe jetzt noch eine teilbare Zahl k in unserer Liste, dann müsste k also das Produkt zweier Zahlen sein, die beide größer als 70 wären. Das ist aber nicht möglich, weil k dann größer als 70 wäre. Folglich besteht unsere Liste jetzt nur noch aus Primzahlen.

Bei sehr großen Zahlen muss man sich etwas tieferliegende Gedanken bei der Primzahlberechnung machen - für elementare Zwecke reicht das obige Verfahren aber völlig aus.
E-Mail, Impressum Excel und lineare Gleichungssysteme