Mit welchen Computerprogramm kann man sich alle Primzahlen ermitteln lassen?
In einem Artikel steht, das man mit einem kleinen Computerprogramms sich alle Primzahlen schnell ermitteln lassen können, wie geht so etwas?
14 Antworten
ich hab da mal ein VBA-Makro geschrieben (basierend auf einem angegebenen Link), das füge ich (ungereinigt, enthält meine Kommentare) ein. Es füllt die 65536 Zeilen von SpalteA mit fortlaufenden Primzahlen (letzte 821641).War noch mit 65536 Zeilen, kannst es ja mal mit >1Mio Zeilen in .xlsm versuchen.
Für mich interessanter war eine UDF=User defined Function, die Zahlen analysieren konnte (Primfaktorenzerlegung), das ging recht schnell, aber ab 10^15 spürbar langsamer bis 10^17++, dann war Schluss (wg. der Genauigkeit von xl?). Die Funktion zeichnete die Zahl als Produkt aller Primfaktoren auf und gab Info über Zeit und ggf zu große Zahlen in dieser Form:
51 | 3*#17 # ist Primzahl > Wurzel($F$4)! (0sec)
457818926249957 | 89*2437*#2110805449 #ist Primzahl>Wurzel($F$4)(6sec)
123456789101112000 | '2*2*2*2*2*2*3*5*5*5*2437*#2110805449 # ist Primzahl > Wurzel($E$4)! (96sec)
152756178123450000 | 2*2*2*2*2*2*2*2*31*45439*#3.423.612.103 # ist Primzahl > Wurzel($F$4)! (359sec)
Ausserdem zeichnet sie die wachsende Kette schrittweise im Direktfenster auf, Du kannst so eine Menge Befehle lernen, falls Du das willst.
ich hage das Auflistungsmakro im 1. Kommentar an, die Funktion im zweiten, ggf weitere Kommentare wären dann aktuelle Äusserungen.
Option Explicit: Option Base 1 '<==wichtig!
Function PrimZahlKetteStd(Zahl As Range) 'funktioniert auch mit sehr großen Zahlen ausreichend schnell (10^15, dann merklich langsamer)
Dim i, Kette, Quo, Start: Start = Time 'Start nicht essentiell, dient zur Zeitanzeige ---auch Quo ü'flüssig, könnte auch mit Zahl weiterrechnen
Quo = Zahl: Debug.Print Zahl.Address(external:=True) & " = " & Quo & " Start:" & Now() '---nicht essentiell---
For i = 2 To Int(Zahl ^ 0.5)
nochmal:
If Int(Quo / i) = Quo / i Then Quo = Quo / i: Kette = Kette & "*" & i: Debug.Print Quo & " " & Kette: GoTo nochmal
Next i '______________________________________________________________- î nicht essentiell!---------------------- ____________
If Quo > 1 Then
PrimZahlKetteStd = Mid(Kette, 2, 999) & "*#" & Format(Quo, "#,##0") & " # ist Primzahl > Wurzel(" & Zahl.Address & ")! (" & Round((Time - Start) * 24 * 60 * 60, 0) & "sec)"
Else '________________________________________________________________________________________________ î nicht essentiell!-----------------------------------
PrimZahlKetteStd = Mid(Kette, 2, 999)
End If: Debug.Print Now() & " Diff=" & Round((Time - Start) * 24 * 60 * 60, 0) & "sec)" 'nicht essentiell
End Function 'getestet:123456789101112000 => 2*2*2*2*2*2*3*5*5*5*2437*#2110805449 # ist Primzahl > Wurzel (96 sec)
Da dieser verschlimmbesserte Editor hier alle Umbrüche schluckt, hoffe ich, dass ich alle gefiunden habe zum Wiedereinfügen: es ist ein Graus!
kopiere die obigen Codes und füge sie in ein Modulblatt ein. Nochmals: beachte: am Kopf des Modulblatts einfügen:
Option Explicit: Option Base 1 '<==für beide Codes wichtig!
viel Spass und gräm Dich nicht, wenn Du nicht alles kapierst: ich hab selbst eine ganze Weile dazu gebraucht und erst dann zu verfeinern angefangen!
bei der letzten Zahl ist was durcheinandergekommen, müsste heissen:
15275617812345000 | 2*2*2*3*5*5*5*5*11*29*#3.192.396.617 # ist Primzahl > Wurzel($F$4)! (126sec),
d. h.3,xx Milliarden ist die Primzahl, die übrigbleibt, wenn die anderen Primfaktoren wegdividiert sind.
Anfangszahl ist 1,5..E 17 (!)
Danke für den Stern!
vllt doch noch ein paar Erklärungen, zuerst zum 1. Programm:
x(65536, 1) ist eine einspaltige Matrix. Damit wird das zeitraubende For Each Zelle in ...Columns(1) mit den zugehörigen Einzel-Adressaufrufen umgangen. Diese Matrix wird am Schluss in die Spalte A kopiert mit Range("A1:A65536") = x
Loop Until Not p(lngP) : bei Do until muss ja ein WAHR folgen, damit abgebrochen wird. p(lngP) muss also zum Abbruch 0 (FALSCH) werden, damit Not... WAHR wird.
Genau blick ich da aber selbst nicht durch, da waren echte "Eggheads" am Werk. Die Methode heißt irgendwas mit "Kamm" (Sieb des Eratosthenes, optimiert als Kiebart-Kamm etc., versteh ich aber selbst nicht so genau. Nur damit du weißt, nach was Du gugln könntest.)
zum 2. Programm:
Obergrenze ist Wurzel Zahl, denn diese zum Quadrat ist ja die Zahl
Es wird zunächst durch 2 geteilt. Int(Quo / i) = Quo / i testet, ob ein Rest vorhanden ist. Wenn ja, ist die Faktorenanzahl 2 erschöpft, es kommt der nächste Teiler dran (3). Danach springt i nicht auf die nächste Primzahl, sondern auf die nächste Zahl, da diese aber durch die Primfaktoren zuvor schon ausgeschöpft ist, sofort weiter, bis wieder ein Teiler kommt, der nur eine Primzahl sein kann! Das ganze ist brût force und wenig intelligent, aber es funktioniert ausreichend schnell.
Das wars auch schon. Der Rest ist das Aneinanderhängen der Faktoren, die Darstellung im Direktfenster und das Übertragen in die Zelle.
Ja, man kann schnell die Primzahlen auflisten. Es sind zwar unendlich viele, aber um beispielsweise alle Primzahlen in {1;2;…;n} aufzulisten, kann man dies in ≤√n-Schritte erledigen:
SIEB ⟵ [2:n]
PRIM ⟵ []
q ⟵ 1
m ⟵ sqrt(n)
WÄHREND q < m :
q ⟵ Min(SIEB)
PRIM ⟵ [PRIM, q]
I ⟵ find(mod(SIEB,k)!=0)
SIEB ⟵ SIEB(I)
ENDE
PRIM ⟵ [PRIM, SIEB]
hier eine Erklärung:
# speichere in SIEB die Zahlen zw. 2 und n
# speichere in PRIM ein leeres Array.
# Lemma: das Minimum von SIEB ist stets
die nächst größte Primzahl
# finde alle Zahlen in SIEB,
die nicht durch q teilbar sind
und reduziere das SIEB darauf.
# Durch die Schleife werden alle Vielfache
der Primzahlen unter √n wurden entfernt.
# Lemma: Die übrig gebliebenen Zahlen sind prim.
Wie man sieht ist der Algorithm extrem einfach und lässt sich in √n Schritte durchführen (oder höchstens √n · √n wenn man dem Schritt SIEB ⟵ SIEB(I) maximal n/q zuschreibt).
Mathematisch ist es nicht möglich alle Primzahlen zu bestimmen. Tatsächlich ist es nicht mal möglich eine Unendlichkeit der Primzahlen zu beweisen.
Allerdings kannst du eine Zahl auf verschiedene Methoden darauf testen, ob sie eine Primzahl ist oder nicht.
(Verschiedene Mehtoden findest du hier: https://de.wikipedia.org/wiki/Primzahltest )
Es ist demnach möglich alle Primzahlen in einem Gewissen Zahlenraum zu bestimmen. Je nach Computerleistung und Geduld kann man diesen Zahlenraum beliebig groß Wählen.
Man kann mit ein bisschen Programmierkenntnisse sich ein kleines Tool selber schreiben.
Hier mal ein kleines Tool um zu testen ob eine Zahl eine Primzahl ist:
Option Explicit
Sub
Primzahl()
Dim
x
As Double
Dim
prim
As Double
Dim
a
As Double
Dim
b
As Double
b = 0
x = Application.InputBox(prompt:=
"Bitte geben Sie eine Zahl ein."
& _
"Wir werden sehen ob es sich um eine Primzahl handelt."
, Type:=1)
If
x = 1
Then
MsgBox (
"Eine Primzahl muß einen Wert über 1 haben"
)
Exit Sub
End If
For
prim = 1
To
x
a = x / prim
If
a = Int(a)
Then
b = b + 1
End If
Next
If
b > 2
Then
MsgBox (x &
" ist keine Primzahl"
)
Exit Sub
Else
MsgBox (x &
" ist eine Primzahl"
)
End If
End Sub
Das ist in VBA und kann als Makro in Excel verwendet werden. Gerne benutzen und umschreiben!
Tatsächlich ist es nicht mal möglich eine Unendlichkeit der Primzahlen zu beweisen.
Das ist leider Quatsch, das ist längst bewiesen, und sogar ziemlich einfach, durch einen Widerspruchsbeweis (den kann man verstehen, sobald man weiß, was eine Primzahl ist):
- Nehmen wir an, es gäbe nur endlich viele Primzahlen, d. h. man kann eine Liste aller Primzahlen aufstellen.
- Daraus folgt, dass es eine größte Primzahl p gibt.
- Wenn man nun alle existierenden Primzahlen miteinander multipliziert und dazu 1 addiert, so ist das Ergebnis z auf jeden Fall größer als p, dürfte nach 2. also keine Primzahl sein.
- Versucht man nun aber, z durch eine der bekannten Primzahlen zu teilen, wird sich (nach Konstruktion) immer der Rest 1 ergeben. Das bedeutet, z ist eine Primzahl, die aber nicht in unserer Liste aller Primzahlen vorkommt.
- Demnach muss die Annahme, die Liste enthalte alle Primzahlen, und damit die Aussage, es gäbe nur endlich viele, falsch sein.
Da hast du wohl was falsch verstanden.
Es gibt unendlich viele Primzahlen. man kann sie also nicht alle berechnen. Und je höher die Zahl desto länger braucht es, sie zu berechnen.
Es gibt - wie in der anderen Antwort geschrieben - unendlich viele Primzahlen, und vor allem große Primzahlen sind schwer zu berechnen.
Aber es gibt ganz clevere Ansätze, um Primzahlen "mit hoher Wahrscheinlichkeit" entdecken zu können. Dafür gibt es auch Bibliotheken für diverse Programmiersprachen.
Zum Beispiel kannst du Funktionen mit ähnlichem Namen wie "is_probable_prime()" oder so ähnlich benutzen, um zu überprüfen, ob eine Zahl (hächstwahrscheinlich) prim ist, oder nicht.
Diese Funktionen haben aber immer eine - wenn auch geringe - Fehlerrate. Eine Funktion, die dir mit 100%iger Sicherheit sofort mitteilt, ob eine Zahl prim ist, würde so ziemlich alle gängigen asymmetrischen Verschlüsselungsmethoden zu Nichte machen, und die Mathematik revolutionieren.
Bis jetzt, wurde so eine Funktion noch nicht gefunden, und sehr sehr viele Mathematiker haben sich darüber schon den Kopf zerbrochen, wobei einige sogar wahnsinnig geworden sind.
Das Ganze ist kein leichtes Thema! Man kann nicht einfach so überprüfen, ob eine Zahl prim ist, oder nicht. Es sei denn, die Zahl ist sehr klein. :)