Zahl mit 10 mio-ziffern in c\c++

Ihr meint, ihr habt einen schnelleren Algorithmus als auf http://www.mersenne.org ? Interessant...

Deren Zeug ist so krank optimiert und getuned, da muss einem schon was sehr geniales einfallen, damit man noch schneller wird.

ich hab nicht behauptet das es schnellere als andere algos ist... aber ich hab mir hald dass noch dazu überlegt:

also wenn man herausfinden will ob eine zahl ein primzahl ist muss man sie durch alle anderen primzahlen dividieren welche kleiner als sie ist...

dann gibts noch ne kleine verbesserung das man einfach nur di hälft von den primzahlen nimmt und sogar ein drittel geht auch noch....

so ich hab mir aber was anderes überlegt .. wenn man sich schnell eine primzahl tabelle mach in excel und dann noch di hochrechnungswerte bis hoch 4 hinschreibt... kann man herausfinden das man zahlen bis 3000 nur mit 2,3,5,7,11,13..57, 59 wenn ich mich nicht verrechnet habe.. und mehr sind das nicht... wenn wir jetzt einfach eine tabelle machen mit allen hochgerechneten primzahlen di mehr als 10mil zeichen haben müssen wir nichtmehr dividieren sondern müssen nur noch vergleichen .. und das geht ja schneller das gibts nämlich auch noch ein paar tricks..... versteht ihr was ich meine?

jamjamjam

bin mir bei deinem text jetzt nicht bei allen punkten sicher was du meinst, es ist natürlich klar, daß du, wenn du eine zahl n prüfen willst, nicht durch alle primzahlenzahlen [2..n] dividieren mußt, sondern nur durch [2..√n]

es gibt eine formel, die dir hilft abzuschätzen, mit wievielen primzahlen du es zu tun haben wirst: http://www.mathpages.com/home/kmath032.htm

wie wär es wenn wir so eine art benchmark realisieren, der 8moi stellige primzahlen berechnet.
Der algorithmus wär eh nicht so schlecht

ich stehe jetzt irgendwie auf der leitung - aber versuchen wir es mit einem einfachen beispiel: nehmen wir an, ich suche eine primzahl mit 5 oder mehr stellen, wie gehe ich da laut deiner tabelle vor?

und wie verifizierst du die erste spalte der tabelle ohne zu dividieren ?
und wird die tabelle nicht sehr schnell irsinnig groß, wenn jede zahl darin mehrere megabyte groß ist ?
und: wenn ich eine primzahl mit irgendwas multipliziere, ist sie keine primzahl mehr - was hab ich übersehen ?

Ist 6 dann auch eine Primzahl? Es ist ja weder 2*2 noch 3*3.

so ... ich arbeite an dem ganzen auch mit (ich bin für den server zuständig) ...

und da hab ich mir gestern überlegt wie man einen zahl mit 11 mil. stellen an einen client versenden kann:

mhm ... es gibt 2 wege ...

1. Binär: 4,6 Mb (zu groß für eine 56k Leitung)
2. String: 11 Mb (auch zu groß ...)

frustriert hab ich das verworfen und hab ein bisschen mit einer zip library gespielt und als ich fertig war, hab ich zum testen die txt datei verpackt die 11mb hatte ... und siehe da: die zip ist 27,1 KiloByte groß! ... ich zip die textfile einfach und versende sie dann *äähää* ... und der client - für den ich auch wahrscheinlich zuständig bin (wer sonst kann schon meine librarys benutzen) - muss das teil wieder entpacken ...

ich hab mir dann ein paar zip libraries besorgt und deren packungs geschwindigkeit berechnet:

-- addZIP (die allererste version): 1 Sekunde und 30 MlSec
-- BSZip: 2 Sekunden irgendwas
-- QuickZip: 3 Sekunden und 50 MlSec

ich nehm jetzt die addZIP und führe damit ein paar tests durch ...