VB: Ist eine Zahl eine Primzahl?

Primzahlen faszinieren seit Jahrtausenden die Menschen und Mathematiker. Sie sind durch keine andere Zahl teilbar, ohne das ein Rest auftritt. Deshalb finden diese Zahlen vorallem bei der Verschlüsselung von Informationen Verwendung. Der Horror jedes sicherheitsbewussten Menschen ist, dass die Mathematiker und Informatiker irgendwann eine Methode finden, um Produkte aus Primzahlen innerhalb kurzer Zeit wieder in Ihre Faktoren zu zerlegen, was bisher noch äußerst zeitaufwendig ist und dadurch asymmetrische Algorythmen wie z.B. RSA (zu dem auch PGP zählt) ohne den richtigen Schlüssel unknackbar macht.
Ob Sie einen solchen Verschlüsselungsalgorhytmus nachbilden wollen oder in Ihren kleinen selbstprogrammierten Taschenrechner einfach eine neue Funktion integrieren wollen, Sie müssen herausfinden, welche Zahlen Primzahlen sind und welche nicht...

Bewertung dieses Tipps:

(bewertet von insgesamt 45 Besuchern)

Etwas Mathematik hilft uns hier weiter

Mit Hilfe der folgenden kleinen und noch relativ simplen Funktion ist es Ihnen möglich, eine bestimmte Zahl auf Ihre Unteilbarkeit zu prüfen. Da hier nur reine Berechnungen durchgeführt werden müssen, ist die Verwendung von API-Funktionen also völlig unnötig:

Function IsPrimeNumber(ByVal Number As Long) As Boolean
   Dim Counter As Long

   If Number Mod 2 = 0 Or Number = 1 Then 'Wenn die angegebene Zahl
      If Number <> 2 Then                 'durch 2 teilbar ist (jedoch
         IsPrimeNumber = False            'ungleich 2) oder gleich 1 ist,
         Exit Function                    'ist es keinesfalls eine Primzahl
      End If
   End If

   For Counter = 1 To Number - 1 Step 2 'Eine Schleife von
      If Number Mod Counter = 0 Then    '1 bis zur angegebenen
         If Counter <> 1 Then           'Zahl - 1 durchlaufen,
            IsPrimeNumber = False       'wobei jede 2. Zahl aus-
            Exit Function               'gelassen wird, da die
         End If                         'Teilbarkeit durch 2 bereits
      End If                            'geprüft wurde. Wird ein
   Next Counter                         'Teiler <> 1 gefunden, ist
                                        'die Zahl keine Primzahl.
   IsPrimeNumber = True
End Function

Ihre Geschwindigkeit gewinnt diese Funktion vorallem einer Tatsache ab: Ist eine Zahl durch eine andere Zahl teilbar, die selber kleinere Teiler besitzt, so ist die Zahl keine Primzahl. Durch die Prüfung auf die Teilbarkeit durch 2 direkt zu Beginn der Prozedur wird so also jede 2. Zahl gleich ausgeschlossen. Diese Prozedur ließe sich mit einigen Modifikationen auch auf die Zahl 3 usw. erweitern, jedoch wäre dies mit weniger bzw. negativem Zeitgewinn verbunden.

Alle Primzahlen bis zur Zahl X ermitteln

Wollen Sie alle Primzahlen bis zu einer bestimmten Zahl errechnen, so ist dies unter Verwendung der obigen Funktion mit relativ wenig Aufwand verbunden. Der folgende Code listet alle Primzahlen bis 10.000 in der ListBox "List1" auf - und das in knapp 330 Millisekunden auf einem Celeron-Prozessor von Intel mit 400 MHz (in kompilierter Form):

Dim Counter As Integer

BisZurZahl = 10000 'Alle Primzahlen bis 10.000 ermitteln
For Counter = 1 To BisZurZahl
   If IsPrimeNumber(Counter) Then 'Die Zahl ist eine Primzahl, also
      List1.AddItem Counter       'rein damit in die ListBox
   End If
Next Counter

Quellen: SHADOWare.de
Letzte Änderung: 19.07.01