---

Geschrieben von scr!pTk!d am 02.05.2003 um 19:18:

  Primzahlen

um zu prüfen ob eine zahl prim ist oder nicht, muss man alle primzahlen bis zur quadratwurzel durch die zahl dividieren und auf reste prüfen. wenn ich jetzt eine sehr große zahl auf ihre "primheit" prüfen will, also z.b.
2^1024 + 1, muss ich durch alle primzahlen bis 2^512
dividieren. angenommen es wären 10 ^ 9. dann bräuchte ich für das array, in welche ich die primzahlen ablegen muss 10 ^ 9 * 4 byte (bei integer vars in c), 3,8147 gigabyte (!!!). wenn ich andererseits durch alle zahlen dividiere um das speicherproblem zu umgehen habe ich 2 ^ 512 - 1 divisionen. wie kann ich das problem lösen?

---

Geschrieben von phlox81 am 02.05.2003 um 19:31:

 

Für was brauchst du so große zahlen ?
Wenn würde man das mit einer Datenbank dann machen...

Devil

---

Geschrieben von Compuholic am 03.05.2003 um 00:17:

 

Wenn Du nur eine vorhandene Zahl testen willst ob sie eine Primzahl ist gibt es eine Möglichkeit. Algorithmen wie RSA benötigen ja auch Routinen um in annehmbarer Zeit Primzahlen zu erzeugen. Ein Beispiel dafür ist der Rabin-Miller Algorithmus. Aber es gibt noch eine Reihe weiterer die mir aber nicht genau bekannt sind.

Vielleicht hilft dir das hier:
http://rhlx01.rz.fht-esslingen.de/projects/krypto/prim/prim.html

Aber wenn Du eine Zahl faktorisieren willst bleibt Dir nur der Weg des Ausprobierens.

---

Geschrieben von scr!pTk!d am 03.05.2003 um 00:39:

 

@devil: es geht nur um einen kontest mit einem freund, wer das schnellere programm schreibt, deshalb wäre auch eine datenbank unsinnig (hohe zugriffszeit etc)

@compuholic: ich will keine zahlen faktorisieren(ich habe keinen supercomputer zuhause). es ging mir nur darum
einen schnellen algorithmus zu bekommen. die in dem link beschriebenen scheinen sehr gut zu sein
vielen dank

---

Geschrieben von CDW am 03.05.2003 um 11:16:

 

das mit der Quadratwurzel ist schojjn richtig, aber du kannst auch noch einiege verbesserungen machen:
nach dem durch zwei dividiert wurde, kann man den index nur noch mindestens um 2 erhöhen.
Wir hatten hier mal auch den kontest, schau da die Lösungen nach zumindest dauert damit ne Zahlüberprüfung von einer (extra dafür erzeugten)Primzahl die etwa 2^32 groß ist weniger als 1ms (nicht messbar).Und man kommt dann ohne Array aus.