  |
|
|
 |
 Primzahlen |
scr!pTk!d 
Member
Dabei seit: 10.11.2002
Beiträge: 276
 |
|
| 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?
__________________
ceterum censeo carthaginem esse delendam
|
|
02.05.2003 19:18 |
|
|
phlox81
Bote des Lichts und Moderator
Dabei seit: 19.10.2002
Beiträge: 3.028
Herkunft: Irgendwo im Nirgendwo
|
|
Für was brauchst du so große zahlen ?
Wenn würde man das mit einer Datenbank dann machen...
Devil
__________________
Intelligenz ist eine Illusion des Menschen
phlox81.de | codenode.de
|
|
|
02.05.2003 19:31 |
|
|
Compuholic
knows where he wants to go tomorrow
Dabei seit: 19.10.2002
Beiträge: 819
Herkunft: München
|
|
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/projec.../prim/prim.html
Aber wenn Du eine Zahl faktorisieren willst bleibt Dir nur der Weg des Ausprobierens.
|
|
|
03.05.2003 00:17 |
|
|
scr!pTk!d
Member
Dabei seit: 10.11.2002
Beiträge: 276
Themenstarter 
|
|
@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
__________________
ceterum censeo carthaginem esse delendam
|
|
|
03.05.2003 00:39 |
|
|
|
|
|
|
|