Primzahlen

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo,

es gibt wahrscheinlich tausende Algorithmen, mit denen man Primzahlen „berechnen“ kann.
Jedenfalls hab ich bei Google viele gefunden.

So wie ich das sehe beruhen die meisten Algorithmen darauf, zu testen, ob eine Zahl eine Primzahl ist. Wenn man den Test also
x-mal auf die Zahl anwendet, dann ist es mit entsprechender Wahrscheinlichkeit eine Primzahl…

Für mich sieht das etwas umständlich aus.
Wie ihr also meinen Ausführungen entnehmen könnt habe ich keine Mathmatik studiert.

Also hier meine Frage. Gibt es eine Möglichkeit möglichst schnell an alle Primzahlen zwischen 0 und x zu kommen ?(berechnender Weise)

Ich hab da eine wahnwitzige Idee, für die ich die Primzahlen brauche…

Danke im Vorraus
Karsten

PS: Gibt es vielleicht irgendwo schon eine Liste mit allen Primzahlen, die schon ermittelt wurden ?

#2

Moin

es gibt wahrscheinlich tausende Algorithmen, mit denen man
Primzahlen „berechnen“ kann.
Jedenfalls hab ich bei Google viele gefunden.

jupp, und jeder ist auf ein anderes Gebiet spezialisiert. (die mit dem (2^n)-1-Ansatz sind i.A. am schnellsten)

So wie ich das sehe beruhen die meisten Algorithmen darauf, zu
testen, ob eine Zahl eine Primzahl ist. Wenn man den Test also
x-mal auf die Zahl anwendet, dann ist es mit entsprechender
Wahrscheinlichkeit eine Primzahl…

einzige bekannte Möglichkeit.

Für mich sieht das etwas umständlich aus.
Wie ihr also meinen Ausführungen entnehmen könnt habe ich
keine Mathmatik studiert.

jupp, man merks an der Frage die jetzt kommt.

Also hier meine Frage. Gibt es eine Möglichkeit möglichst
schnell an alle Primzahlen zwischen 0 und x zu kommen
?(berechnender Weise)

nein, berechen in dem Sinn kann man Primzahlen nicht. Wenn jemand mal die Formel findet (es wird daran geforscht, so eine Formel wäre SEHR praktisch…) dürfte das die moderne public/private-Key Kryptographie auslöschen, oder zumindest sehr viel unsicherer machen.

PS: Gibt es vielleicht irgendwo schon eine Liste mit allen
Primzahlen, die schon ermittelt wurden ?

frag google. Die Listen wurden mal als CD-set verkauft, den Anbieter gibts aber nicht mehr.

cu

#3

Moin

hatte was vergessen:

http://www.utm.edu/research/primes/

PS: Gibt es vielleicht irgendwo schon eine Liste mit allen
Primzahlen, die schon ermittelt wurden ?

die ersten 1000 stehen direkt auf der Seite.

cu

#4

Hi,

habe vor ca. 3 Monaten irgendwo ne Formel gesehen
(jaja die gibt es), die testet ob eine
gegebene Zahl eine Primzahl ist. Also ohne Schleifen
etc. Weiß nur nicht mehr wo das war.

Falls es so dringend ist suche ich nochmal…

Für den Fall, daß das völlig egal ist (habe nämlich den
ganzen Thread nicht mitgekriegt) tuts mir leid,
daß ich geantwortet habe…

Alex

#5

Hallo,

die Frage ist hier schon mal aufgetaucht (ähnlich), daher ein Verweis auf meine damalige Antwort:
http://www.wer-weiss-was.de/cgi-bin/forum/showarchiv…

Ciao, Bill

#6

Hi,

habe vor ca. 3 Monaten irgendwo ne Formel gesehen
(jaja die gibt es), die testet ob eine
gegebene Zahl eine Primzahl ist. Also ohne Schleifen

a(0) := 3
a(1) := 0
a(2) := 2
a(n) := a(n-3) + a(n-2) | n € |N > 2

n ist prim, wenn a(n)/n € |N ist. a(n) lässt sich auch ohne Abhängigkeit der früheren a(m) (m € |N