Code: Alles auswählen
n = 31622
sieve = range(1,n+1,2)
max_divider = 88
# ...SPOJ - PRIME1 - Primzahlengenerator
Wenn n und max_divider sowieso statische werte haben, dann kannst du denen auch gleich diese Werte direkt zuweisen (dir scheint Gescheindigkeit ja wichtig zu sein):
Hallo!
Ich war auch mal Primeln sieben und habs auf den 2. Platz geschafft, aber nur mit psychedelischem Turboknopf.
@nummerix:
Hut ab, Du hast da ziemlich die Nase vorn. Mit Turbo würdest Du sicher um die 0.20 wenn nicht gar drunter kommen. Mein Problem ist das obere Sieb, das ist mir nicht so richtig performant gelungen (ich hatte vorher ohne psyco 1.12). Vllt. packts mich nochmal und ich setze mich mit Papier und Bleistift hin wie Du das empfohlen hattest. Dein Abstand spricht jedenfalls Bände, mir fehlte da die zündende Algorithmus-Idee. Wäre mal interessant wie schnell Dein Verfahren in C/C++ ist.
Grüße, Jerch
Ich war auch mal Primeln sieben und habs auf den 2. Platz geschafft, aber nur mit psychedelischem Turboknopf.
@nummerix:
Hut ab, Du hast da ziemlich die Nase vorn. Mit Turbo würdest Du sicher um die 0.20 wenn nicht gar drunter kommen. Mein Problem ist das obere Sieb, das ist mir nicht so richtig performant gelungen (ich hatte vorher ohne psyco 1.12). Vllt. packts mich nochmal und ich setze mich mit Papier und Bleistift hin wie Du das empfohlen hattest. Dein Abstand spricht jedenfalls Bände, mir fehlte da die zündende Algorithmus-Idee. Wäre mal interessant wie schnell Dein Verfahren in C/C++ ist.
Grüße, Jerch
Gratuliere!jerch hat geschrieben:Hallo!
Ich war auch mal Primeln sieben und habs auf den 2. Platz geschafft, aber nur mit psychedelischem Turboknopf.
@nummerix:
Hut ab, Du hast da ziemlich die Nase vorn. Mit Turbo würdest Du sicher um die 0.20 wenn nicht gar drunter kommen. Mein Problem ist das obere Sieb, das ist mir nicht so richtig performant gelungen (ich hatte vorher ohne psyco 1.12). Vllt. packts mich nochmal und ich setze mich mit Papier und Bleistift hin wie Du das empfohlen hattest. Dein Abstand spricht jedenfalls Bände, mir fehlte da die zündende Algorithmus-Idee.
Mein Algorithmus - jedenfalls, der, der aktuell noch die Pole-Position innehat - dürfte mit psyco (wenn überhaupt) nur unwesentlich schneller werden, weil er so optimiert ist, dass psyco da nichts oder wenig bringt. Aber das probiere ich erst aus, wenn es ohne psyco nicht mehr für Platz 1 reicht ...
Was meinen Algorithmus angeht, so ist der im Grunde ziemlich schlicht. Es gibt zwar modernere Siebverfahren (z.B. Sieb von Atkins), aber die habe ich nicht eingesetzt, sondern bin beim bewährten Eratothenes geblieben.
Das finde ich gerade das Faszinierende daran - und das war bisher bei fast allen SPOJ-Aufgaben so, mit denen ich mich beschäftigt habe: Die besten Lösungen waren meistens auch die schlankesten, jedenfalls dann, wenn ich auf psyco verzichtet habe.
Wenn jerch es aus Bescheidenheit nicht selbst tut, mach ich es mal:
Er ist der neue Primzahlkönig! Mit 0.25 s hat er das mit Abstand schnellste Python-Programm zur Lösung von PRIME1. GRATULATION!
Wir warten auf HerrHagen ...
Er ist der neue Primzahlkönig! Mit 0.25 s hat er das mit Abstand schnellste Python-Programm zur Lösung von PRIME1. GRATULATION!
Wir warten auf HerrHagen ...
