SPOJ - PRIME1 - Primzahlengenerator

[numerix]

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

Dann wäre das ganze auch langweilig

[Graf Wasserrutsche]

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.

[numerix]

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

[HerrHagen]

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

[numerix]

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]

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.

[Craven]

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?

[Leonidas]

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.

[BlackJack]

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.

[numerix]

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.

[Graf Wasserrutsche]

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

[Craven]

Wird Psyco denn überhaupt akzeptiert von SPOJ?

[Graf Wasserrutsche]

Bei Adding Reversed Numbers (ADDREV) hat es funktioniert.

[numerix]

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]

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!