[Mathe] Primzahlen

[kFeHaG]

Hi
ich und n paar Kumpels suchen zur Zeit ne Formel bzw ein Weg ein Programm zu programmieren mit dem man Primzahlen ausrechnen kann, bzw. generell Formeln um Primzahlen festzustellen. Warum wir das machen? Just 4 Fun ^^

Wir haben schon ein Programm, mit dem man überprüfen kann ob eine Zahl eine Primzahl ist:
-> Zahl x wird eingegeben -> Zahl x wird durch alle Zahlen geteilt die < x sind.
Wenn die Zahl x dann nur durch 1 und x teilbar ist, ist es eine Primzahl und das Programm gibt das aus.

Ein anderer Ansatz von uns war:
n! -1 = Primzahl
Das stimmt bis n=7 (nicht mehr sicher)

Weiter überlegten wir dann
2 n! -1 = Primzahl
Das gilt (sofern ich mich erinnere) bis n=8

(Wir hofften dass es für > 3 n! -1 = Primzahl < bis n=9 stimmt.. und > 4n!-1< bis n = 9... das wär ideal und wir hätten ne (vermutliche) Regelmäßigkeit, allerdings stimmt das nicht)

Jetzt wollte ich mal fragen, ob ihr irgendwelche Ansätze kennt, mit dem man eine Regelmäßigkeit feststellen kann, wann eine Zahl eine Primzahl ist.
Wir suchen generell nach neuen Methoden die wir programmieren können, denn
"-> Zahl x wird eingegeben -> Zahl x wird durch alle Zahlen geteilt die < x sind.
Wenn die Zahl x dann nur durch 1 und x teilbar ist, ist es eine Primzahl und das Programm gibt das aus."
dauert zu lange zum berechnen^^

Greetz, Chris

 

[MrToiz]

Solltet ihr tatsächlich eine Formel finden, würde ich dir raten, sie nicht sofort hier zu posten Seit Jahrtausenden wird nämlich danach gesucht, und niemand hat sie bis jetzt gefunden. Dementsprechend winken mehrere Millionen Prämie demjenigen, der eine Formel findet

Schau mal bei Wikipedia, da findest du recht viele Infos!

 

[tdnpf]

es reicht, wenn ihr x mit allen Primzahlen < sqrt(x) testet. Habt ihr schon google und wikipedia gefragt?

 

[joschilein]

Es gibt natürlich keine allgemeingültige Formel um Primzahlen auszurechnen, deswegen rattern auf der ganzen Welt ja auch ein paar Millionen teure Supercomputer, die nichts anderes machen als Primzahlen zu errechnen.

Und Ansätze für Algorithmen? *hüstel* Viel Spaß

 

[blue.shift]

Eine gute Heuristik ist der kleine Satz von Fermat, mit dessen Verfahren man definitiv sagen kann, dass eine Zahl keine Primzahl ist. Diejenigen, welche übrigbleiben sind mit relativ großer Wahrscheinlichkeit prim (aber eben nicht sicher). Für die ersten 20 oder 30 Primzahlen funktioniert das ganz gut, danach wird das wegen der Exponentiation für reguläre 32 oder 64 bit Datentypen schon heikel. Der große Satz von Fermat bietet ebenfalls ein bisschen Zahlentheorie.

Gruß Robin