Wer kann die schnellsten Primzahlen?

rapso

Shade Of Mine schrieb:

Sorry falls ich die Frage/Antwort überlesen haben sollte:

Wieviele Zahlen bekomme ich denn als Eingabe. Sprich: wo liegt die Obergrenze? Allzuviele, sprich 2^32 werden es ja wohl nicht sein, weil dann das testen zu lange dauert, oder?

Mehr als 2^32 würde meinen Algo tot machen, also lieber weniger nehmen

falls du die range meinst, die lag bei 2^63-1 afaik.

rpaso->greets();

volkard

Shade Of Mine schrieb:

Wieviele Zahlen bekomme ich denn als Eingabe. Sprich: wo liegt die Obergrenze? Allzuviele, sprich 2^32 werden es ja wohl nicht sein, weil dann das testen zu lange dauert, oder?

als eingabe kriegste so 3 oder 10 zahlen. die definieren aber nur die zufallszahlengenerator und irgendwie (vermutlich von dir nicht auslesbar) die anzahl der zu testenden zahlen.

falls du nur fürchtest, daß dein cache überläuft, ich kann mir nicht vorstellen, daß es 2^32 zahlen werden. aber ich weiß ja nicht, wie ausgefuchst schnell eure verfahren werden. wenn ihr 2^32 zahlen in 10 minuten testen könnt, kann es passieren, daß die sequenz auch 2^32 lang wird.

Mehr als 2^32 würde meinen Algo tot machen, also lieber weniger nehmen

falls es nur ein cache ist, den kannste zur not immer nach 2^32 einträgen flushen.
ach, riskier es, würde ich sagen. wenn ich richtig sehe, werden die zahlen über 2^50 so affig lange rechnen, daß wir froh sein können, in 10 min eine davon zu schaffen.

Shade Of Mine

volkard schrieb:

falls es nur ein cache ist, den kannste zur not immer nach 2^32 einträgen flushen.

Ist aber kein cache.

Mein ganzer Algo baut eigentlich darauf auf, dass ich X zahlen zum testen bekomme wobei X in einem bestimmten Bereich, vorzugsweise <2^32 liegt. Alles darüber wird da nämlich teuerer. Und teurer heisst, dass ich mich dumm und dämlich zahle wenn dann nur 2^10 oder so zahlen kommen...

Ich werde also auf max 2^32 zahlen gehen.

Aber mein Beitrag ist sowieso egal - da ich zu wenig über Primzahlen weiss kann ich eh nicht mit den Profis mithalten (aber spaß habe ich trotzdem daran, und das ist ja das wichtigste).

@rapso:
range ist klar, es ging mir um die Anzahl der Zahlen die ich Testen muss und sagen können muss ob es eine Primzahl ist. Volkard hat mich eh verstanden

energyzer

Ich glaube kaum, dass jemand einen so ausgefuchsten Algo hat, dass er über 2^32
Zahlen in einer nicht mehr messbaren kleinen Zeit schafft Also können wir das
IMHO ruhig als max. Grenze annehmen - Einwände? Andererseits würde ich es gut
finden, wenn die Algos die Überschreitung von 2^32 Zahlen überleben - auch wenn
sie dann langsam werden.

// Edit: Es geht mir um die Anzahl der Zahlen und nicht um deren Größe!

Ponto

EnERgYzEr schrieb:

Ich glaube kaum, dass jemand einen so ausgefuchsten Algo hat, dass er über 2^32
Zahlen in einer nicht mehr messbaren Zeit schafft Also können wir das IMHO
ruhig als max. Grenze annehmen - Einwände? Andererseits würde ich es gut finden,
wenn die Algos die Überschreitung von 2^32 Zahlen überleben - auch wenn sie
dann langsam werden.

Du meinst, dass die Obergrenze von 2^63-1 auf 2^32 gesenkt wird?

Ponto

volkard schrieb:

ach, riskier es, würde ich sagen. wenn ich richtig sehe, werden die zahlen über 2^50 so affig lange rechnen, daß wir froh sein können, in 10 min eine davon zu schaffen.

Das verstehe ich nicht so ganz? Ein trivialer Algorithmus zum Testen von 9223371994482243049 (2^63 -1 = 9223372036854775807) braucht auf meinem P4 2.4 GHz 38 Sekunden. Ich verrate wohl nichts, wenn ich sage, dass der Algorithmus im Grunde so aussieht:

for (unsigned i = 3; i * i < test; i += 2) {
  if (test % i == 0) {
     break;
  }
}

energyzer

Ponto schrieb:

EnERgYzEr schrieb:

Ich glaube kaum, dass jemand einen so ausgefuchsten Algo hat, dass er über 2^32
Zahlen in einer nicht mehr messbaren Zeit schafft Also können wir das IMHO
ruhig als max. Grenze annehmen - Einwände? Andererseits würde ich es gut finden,
wenn die Algos die Überschreitung von 2^32 Zahlen überleben - auch wenn sie
dann langsam werden.

Du meinst, dass die Obergrenze von 2^63-1 auf 2^32 gesenkt wird?

Nein, dass würde den ganzen Spaß nehmen Die Anzahl der Zahlen die ausge-
rechnet werden sollen, könnten wir auf ein max. von 2^32 setzen.

Zarniwoop

Bei mir(WinXp, Dev-C++) zeigt

typedef unsigned long long ulong;
cout << sizeof(ulong);

lediglich 8 byte an. Bei 8*4 = 32 reicht das nicht aus, um Zahlen wie 2^63 zu speichern. Wie kann ich das ändern/mache ich etwas falsch?

Zarniwoop

rapso

Zarniwoop schrieb:

Bei mir(WinXp, Dev-C++) zeigt
typedef unsigned long long ulong;
cout << sizeof(ulong);
lediglich 8 byte an. Bei 8*4 = 32 reicht das nicht aus, um Zahlen wie 2^63 zu speichern. Wie kann ich das ändern/mache ich etwas falsch?

Zarniwoop

wie kommst du auf 4? byte hat 8 bit, also 8*8=64

rapso->greets();

Zarniwoop

Ah sc***** - stimmt!

Man bin ich doof!

Zarniwoop

FireFlow

Ponto schrieb:

volkard schrieb:

ach, riskier es, würde ich sagen. wenn ich richtig sehe, werden die zahlen über 2^50 so affig lange rechnen, daß wir froh sein können, in 10 min eine davon zu schaffen.

Das verstehe ich nicht so ganz? Ein trivialer Algorithmus zum Testen von 9223371994482243049 (2^63 -1 = 9223372036854775807) braucht auf meinem P4 2.4 GHz 38 Sekunden. Ich verrate wohl nichts, wenn ich sage, dass der Algorithmus im Grunde so aussieht:
for (unsigned i = 3; i * i < test; i += 2) {
  if (test % i == 0) {
     break;
  }
}

Ich braue 0,01ms

Ponto

FireFlow schrieb:

Ich braue 0,01ms

Aber nicht für die Schleife. Und dass man mit dieser Schleife keinen Blumentopf gewinnt ist wohl auch klar.

otze

FireFlow schrieb:

Ich braue 0,01ms

mit einer 99,9999999% sicherheit, oder 100%?

FireFlow

otze schrieb:

FireFlow schrieb:

Ich braue 0,01ms

mit einer 99,9999999% sicherheit, oder 100%?

Für kleine Zahlen hab ich 100% bei extrem großen dann eigentlich nicht mehr aber es ist sooooo unrealistisch dass ich dabei etwas falsch erkenne dass ich es schon fast ausschließe. Momentan bastel ich aber noch dran rum.

Jester

FireFlow schrieb:

Für kleine Zahlen hab ich 100% bei extrem großen dann eigentlich nicht mehr aber es ist sooooo unrealistisch dass ich dabei etwas falsch erkenne dass ich es schon fast ausschließe. Momentan bastel ich aber noch dran rum.

Hatten wir nicht genau dieses Vorgehen ausgeschlossen?

FireFlow

Jester schrieb:

FireFlow schrieb:

Für kleine Zahlen hab ich 100% bei extrem großen dann eigentlich nicht mehr aber es ist sooooo unrealistisch dass ich dabei etwas falsch erkenne dass ich es schon fast ausschließe. Momentan bastel ich aber noch dran rum.

Hatten wir nicht genau dieses Vorgehen ausgeschlossen?

Wenn ich damit fertig bin wirds noch bischen langsamer aber ich bekomm es hin dass es keine Fehler gibt.

FireFlow schrieb:

Wenn ich damit fertig bin wirds noch bischen langsamer aber ich bekomm es hin dass es keine Fehler gibt.

Wenn dein Verfahren wirklich so schnell ist, wie du sagst, kannst du die Korrektheit ja mal halbwegs durch einen Vergleich mit meinem Primzahlzählprogramm überprüfen. Zähl mit deinem Programm oben doch einfach auch mal die Primzahlen zwischen 0 und 1.000.000.000. Was da IMHO rauskommen sollte, habe ich weiter oben schon gepostet. Ich bin mir relativ sicher, dass der Wert, den ich da rauskriege korrekt ist.

/me würde das Ergebnis sehr interessieren.

Hier nochmal das IMHO korrekte Ergebnis:

Zwischen 0 und 1000000000 liegen 50847534 Primzahlen.

FireFlow

Gregor@Home schrieb:

Hier nochmal das IMHO korrekte Ergebnis:

Zwischen 0 und 1000000000 liegen 50847534 Primzahlen.

Bin grade bei 60Mio das ghet noch ne Weile *narf-narf*. Ich erwarte aber eher etwas falsches hab grade etwas rumoptimiert und geh davon aus dass ich hier oder da ein Fehler hab. Hab extra die langsame Variante gewählt die nicht auf Wahrscheinlichkeiten aufbaut. Wenn ich fertig bin gibts mein Ergebniss auch.

Woher hast du das Ergebniss?

FireFlow schrieb:

Woher hast du das Ergebniss?

Primzahlen von 0 bis n zählen kann man ja deutlich schneller machen als wenn man eine einzelne Primzahl überprüfen muss. Ich habe da vor Jahren mal ein Programm zum Primzahlzählen geschrieben (Optimizer kann dir dazu auch was erzählen ). Das nutzt letztendlich ein einfaches Sieb des Erathostenes.

Wenn du willst, kann ich auch nochmal die Anzahl der Primzahlen bis zu einer kleineren Obergrenze posten. 100.000.000 oder 10.000.000 oder so.