SPOJ - PRIME1 - Primzahlengenerator

Code-Stücke können hier veröffentlicht werden.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Freitag 13. Februar 2009, 11:40

Leonidas hat geschrieben:Leider gibt es die Quellcodes nirgendwo öffentlich, was aber auch irgendwie verständlich ist.


Dann wäre das ganze auch langweilig :)
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

Beitragvon Graf Wasserrutsche » Freitag 13. Februar 2009, 11:42

Kannst du mir evtl. doch noch weitere Ratschläge geben, wie ich bei dem Primzahlproblem weiterkommen könnte? Ich steck da sowas von fest, dass ich nicht mehr nach vorne und nach hinten weiss.

Oder gib mir nur einen kleinen Tipp. Wenn ich die Liste ja bis 1.000.000.000 befüllen will gibt es einen MemoryError. Wie umgehe ich diesen bzw. wie ermittle ich, bis zu welchem Wert ich überhaupt rechnen muss damit alles nötige abgedeckt ist?

Vielen Dank schonmal.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Freitag 13. Februar 2009, 12:21

Graf Wasserrutsche hat geschrieben:Kannst du mir evtl. doch noch weitere Ratschläge geben, wie ich bei dem Primzahlproblem weiterkommen könnte? Ich steck da sowas von fest, dass ich nicht mehr nach vorne und nach hinten weiss.

Oder gib mir nur einen kleinen Tipp. Wenn ich die Liste ja bis 1.000.000.000 befüllen will gibt es einen MemoryError. Wie umgehe ich diesen bzw. wie ermittle ich, bis zu welchem Wert ich überhaupt rechnen muss damit alles nötige abgedeckt ist?


Wie ich schon in vorherigen Beiträgen geschrieben habe, kann die Lösung nicht so funktionieren, dass man das gesamte Intervall von 1 bis 1 Mrd. in das Sieb steckt. Selbst wenn es keinen Speicherfehler gäbe, wäre das nicht der richtige Weg.

Die Aufgabenstellung ist ja so, dass aus dem gesamten Zahlenbereich bis 1 Mrd. nur 10 Intervalle mit einer Breite von max. 100 000 herausgepickt werden, so dass im ungünstigsten Fall "nur" 1 Mio. Zahlen auf ihre Primalität zu prüfen sind. Oder anders gesagt: Von den 1 Mrd. möglichen zu untersuchenden Zahlen sind garantiert mindestens 999.000.000 Zahlen für die Untersuchung von vornherein uninteressant. In deinem Fall mit dem "Mega-Sieb" untersuchst du die aber trotzdem.

Die Lösung wird also so aussehen müssen, dass du dir die 10 gegebenen Intervalle einzeln vornimmst und ein an dieses Intervall angepasstes Sieb konstruierst.
Hilfreich ist es, wenn man sich dafür zunächst einen kleinen Zahlenbereich nimmt - sagen wir von 30 bis 60 - und sich mit Bleistift und Papier bewaffnet überlegt, mit welcher Zahl dieses Intervalls man die Suche beginnt und welche der enthaltenen Zahlen man überhaupt untersuchen will bzw. muss.

Nur mal so zur Einschätzung der Größenordnung: Ein Programm, das die PRIME1-Aufgabe in unter 0.5 s löst, braucht für die Berechnung der Primzahlen bis 100 Mio. schon länger als 1 Minute. Da die benötigte Zeit für größer werdende Primzahlen alles andere als linear ansteigt, kommt da ordentlich was an Zeit zusammen ...
Benutzeravatar
HerrHagen
User
Beiträge: 430
Registriert: Freitag 6. Juni 2008, 19:07

Beitragvon HerrHagen » Freitag 13. Februar 2009, 21:49

Eins wird mich dann noch interessieren: Wie lang braucht dein Algorithmus eigentlich für den Bereich (1000000000, 1000000000-100000)? Ich weiß nicht so recht wie stark ich meine Lösung einzuschätzen ist und ob des sich lohnt meinen Lösungsansatz weiterzuentwickeln...

MFG HerrHagen
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Freitag 13. Februar 2009, 23:23

HerrHagen hat geschrieben:Eins wird mich dann noch interessieren: Wie lang braucht dein Algorithmus eigentlich für den Bereich (1000000000, 1000000000-100000)? Ich weiß nicht so recht wie stark ich meine Lösung einzuschätzen ist und ob des sich lohnt meinen Lösungsansatz weiterzuentwickeln...


0.12 s auf meinem (fast 8 Jahre alten) Rechner.
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

Beitragvon Graf Wasserrutsche » Mittwoch 18. Februar 2009, 09:22

So, ich habe jetzt alles nochmal über den Haufen geworfen und neu angefangen.

Ich beginne damit eine Liste mit dem Zahlenbereich von m zu n zu füllen.

Jetzt wird auf jeder Seite die ich gefunden habe gezeigt wie man das Problem mit einem Sieb, beginnend mit der Zahl 2 löst, aber nicht, mit einem Sieb welches z.B. mit 35 beginnt. Muss ich nicht trotzdem diverse Zahlen vor dem Bereich ausrechnen, um bestimmte Zahlen in diesem Sieb streichen zu können, oder gibt es da noch eine andere Möglichkeit?

Vielleicht habt ihr ja auch Quellen, mit welchen ich mir das benötigte auch anlesen kann.
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Beitragvon Craven » Mittwoch 18. Februar 2009, 13:10

numerix hat geschrieben:0.12 s auf meinem (fast 8 Jahre alten) Rechner.

Sollen wir es mal mit einem etwas schnelleren CPU testen? :>

Da fällt mir gerade ein, Python 2.5 bzw. 2.6 unterstützen ja noch garkeine Dual Cores, oder?
Zuletzt geändert von Craven am Mittwoch 18. Februar 2009, 14:31, insgesamt 1-mal geändert.

Code: Alles auswählen

q = 'q = %s; print q %% repr(q)'; print q % repr(q)
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 18. Februar 2009, 13:32

Craven hat geschrieben:Da fällt mir gerade ein, Python 2.5 bzw. 2.6 unterstützt ja noch garkeine Dual Cores, oder?

3.0 tut es genausowenig. Wobei, eigentlich ist die Sache etwas komplizierter als das. Siehe Diskussionen zu GIL.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
BlackJack

Beitragvon BlackJack » Mittwoch 18. Februar 2009, 14:10

Jede der drei Versionen unterstützt mehrere Prozessorkerne, wenn man den Code entsprechend schreibt, also zum Beispiel das `multiprocessing`-Modul ab Python 2.6 aus der Standardbibliothek verwendet, oder dessen Vorgänger bei Python 2.5 installiert.

Unter IronPython und Jython sollte man ganz normal mit Threads arbeiten können, da beide kein GIL haben.

@Graf Wasserrutsche: Wenn Du bei einem beliebigen Bereich "aussieben" möchtest, brauchst Du auch die Primzahlen ab 2, und kannst dann alle Vielfachen von denen aus dem Bereich streichen.

Der Witz dabei ist, dass Du zum Beispiel für den Bereich von 50.000 bis 60.000 nicht alle Primzahlen von 2 bis 50.000 brauchst, sondern nur die von 2 bis `x`, wobei `x` *deutlich* kleiner als 50.000 ist.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Mittwoch 18. Februar 2009, 14:35

Graf Wasserrutsche hat geschrieben:Jetzt wird auf jeder Seite die ich gefunden habe gezeigt wie man das Problem mit einem Sieb, beginnend mit der Zahl 2 löst, aber nicht, mit einem Sieb welches z.B. mit 35 beginnt. Muss ich nicht trotzdem diverse Zahlen vor dem Bereich ausrechnen, um bestimmte Zahlen in diesem Sieb streichen zu können, oder gibt es da noch eine andere Möglichkeit?
Vielleicht habt ihr ja auch Quellen, mit welchen ich mir das benötigte auch anlesen kann.


Wenn du die Idee des Siebes wirklich - so durch und durch! - verstanden hast, dann hast du alles, was du brauchst. Schreib dir doch mal das Sieb von z.B. 35 bis 70 auf und führe die dann zu tuenden Schritte manuell durch. Mach dir Gedanken über die Zahlen, die gestrichen werden und wie du an die Zahlen herankommst. Der Rest ist im Prinzip nichts anderes, als eine gründliche Analyse dessen, was du siehst. Und dann die gewonnenen Erkenntnisse in einen Algorithmus umsetzen. :wink:
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

Beitragvon Graf Wasserrutsche » Mittwoch 18. Februar 2009, 15:35

So, habe den Algorithmus jetzt etwas abgewandelt und jetzt lässt er sich auch auf Zahlenräume, welche nicht zwingend mit 2 Anfangen übertragen, doch das Zeitproblem besteht weiterhin.

Hm, jetzt muss ich mich irgendwie an die Zeitoptimierung machen. Ich glaube ich mache mal ne Pause, vielleicht klappts besser wenn ich nach ner Pause wieder an das Problem gehe :)

Code: Alles auswählen

from math import sqrt

import psyco
psyco.full()

def sieve(m,n):
    sieve = range(m,n+1)
   
    max_divider = int(sqrt(n))/2
    curr_divider = 2
   
    while curr_divider <= max_divider:
       
        for i in range(0,len(sieve)):
            if int(sieve[i]) == curr_divider:
                pass
            elif int(sieve[i]) % curr_divider == 0:
                sieve[i] = 0
       
        curr_divider += 1
       
    return sieve
   
for i in sieve(35,70):
    if i != 0:
        print i
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Beitragvon Craven » Mittwoch 18. Februar 2009, 15:39

Wird Psyco denn überhaupt akzeptiert von SPOJ?

Code: Alles auswählen

q = 'q = %s; print q %% repr(q)'; print q % repr(q)
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

Beitragvon Graf Wasserrutsche » Mittwoch 18. Februar 2009, 15:41

Bei Adding Reversed Numbers (ADDREV) hat es funktioniert.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Mittwoch 18. Februar 2009, 16:45

Craven hat geschrieben:Wird Psyco denn überhaupt akzeptiert von SPOJ?


Ja. Du kannst sogar aus den dortigen Angaben über den Speicherbedarf erschließen, ob mit psyco (ca. 37 MB) oder ohne psyco (ca. 4 MB) gearbeitet wurde ...
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

Beitragvon Graf Wasserrutsche » Mittwoch 25. Februar 2009, 15:15

So, nach viel Grübeln und Probieren schaffe ich es immer noch nicht. Bin ja soweit, dass ich nicht immer den gesamten Zahlenraum prüfen muss, sondern noch den, der wirklich durch m und n definiert wird, aber das in so einer unglaublich langen Zeit, dass er immer abbricht.

Ich weiss, oder bin mir ziemlich sicher das ich schon langsam anfange zu nerven. Aber könnt Ihr mir für meinen jetzigen Algorithmus ein paar Tipps geben, oder Punkte ansprechen die ich ändern muss, damit er richtig bzw. schneller funktioniert?

Vielen Dank für eure Mühe!

Wer ist online?

Mitglieder in diesem Forum: __deets__