Wer kann die schnellsten Primzahlen?

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.

FireFlow

Wooh stimmt ich hab über das Sieb was gefunden hab aber keine Implementation. Wär super wenn du mal immer so von 10^n die Anzahl angibst. 1Mrd reicht ja als Obergrenze. Wenn mein Programm bis dahin und darüber stichprobebartig korrekt arbeitet gehe ich davon aus dass es klappt.

Ich muss das noch irgendwie optimieren, naja bin ja Schüler und hab massig Zeit *hihi*

Zarniwoop

Kan man seinen Code auch einrechen, wenn man beim Forumstreffen nicht dabei ist?

Gibt es eigentlich einen Einsendeschluss?
edit: erst lesen, dann posten... steht gleich im ersten Post.

Zarniwoop

Da sind ein paar andere Ergebnisse:

Zwischen 0 und 100000000 liegen 5761455 Primzahlen.
Zwischen 0 und 10000000 liegen 664579 Primzahlen.
Zwischen 0 und 1000000 liegen 78498 Primzahlen.
Zwischen 0 und 100000 liegen 9592 Primzahlen.

Gregor@Home schrieb:

Ich habe da vor Jahren mal ein Programm zum Primzahlzählen geschrieben (Optimizer kann dir dazu auch was erzählen ).

Nein, kann ich nicht.

Optimizer schrieb:

Nein, kann ich nicht.