SPOJ - PRIME1 - Primzahlengenerator

Code-Stücke können hier veröffentlicht werden.
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

Beitragvon derdon » Sonntag 8. März 2009, 19:44

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):

Code: Alles auswählen

n = 31622
sieve = range(1,n+1,2)
max_divider = 88
# ...
jerch
User
Beiträge: 1622
Registriert: Mittwoch 4. März 2009, 14:19

Beitragvon jerch » Montag 9. März 2009, 17:11

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
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Montag 9. März 2009, 17:48

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.


Gratuliere!

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 ... :wink:

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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Mittwoch 11. März 2009, 16:46

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 ...
jerch
User
Beiträge: 1622
Registriert: Mittwoch 4. März 2009, 14:19

Beitragvon jerch » Donnerstag 12. März 2009, 16:07

Danke numerix :oops:

Du hast die Latte aber auch sehr hoch gehängt, zumal ohne psyco.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder