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!

[HerrHagen]

Wie wärs z.B. damit:
Wenn du bspw. schon alle Vielfachen von 3 gestrichen hast brauchst du bei der nächsten Primzahl 5 dann 5*3, 5*6, 5*9 ... nicht mehr streichen.

[numerix]

Wie wärs z.B. damit:
Wenn du bspw. schon alle Vielfachen von 3 gestrichen hast brauchst du bei der nächsten Primzahl 5 dann 5*3, 5*6, 5*9 ... nicht mehr streichen.

Wobei man den Aufwand aber gegeneinander abwägen muss. Möglicherweise wird es teurer, die Werte herauszurechnen, die man nicht erneut streichen muss, als diese einfach nochmal zu streichen.

[Graf Wasserrutsche]

So, jetzt läuft das Sieb von 1 bis 100000 schonmal ne Sekunde schneller. Nicht viel, aber immerhin Habe jetzt den max_divider angepasst und überprüfe die Stelle im Sieb nur, wenn Sie nicht gleich null ist.

Zu dem Tipp, wenn ich zusätzlich noch die nicht zu streichenden Stellen berechne, komme ich dann nicht bei der Programmlaufzeit auf die gleiche Zeit?

Code: Alles auswählen

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 sieve[i] != 0:
                if int(sieve[i]) == curr_divider:
                    pass
                elif int(sieve[i]) % curr_divider == 0:
                    sieve[i] = 0
        
        curr_divider += 1
        
    return sieve

[numerix]

Wie wärs z.B. damit:
Wenn du bspw. schon alle Vielfachen von 3 gestrichen hast brauchst du bei der nächsten Primzahl 5 dann 5*3, 5*6, 5*9 ... nicht mehr streichen.

Wobei man den Aufwand aber gegeneinander abwägen muss. Möglicherweise wird es teurer, die Werte herauszurechnen, die man nicht erneut streichen muss, als diese einfach nochmal zu streichen.

Möchte das nochmal unterstreichen und einmal mehr meiner Begeisterung über Python Ausdruck verleihen: Durch eine kleine Änderung an meinem Code, die lediglich einen der Kernabläuf "pythonischer" macht, ist es gelungen, die bisherige Lösung noch einmal schneller zu machen: Die letzte Fassung war mit 0.40 s SPOJ-Laufzeit ja auch schon nicht gerade langsam, hat das aber nur mit psyco geschafft. Jetzt sind es 0.35 s und zwar OHNE PSYCO. Python ist toll!

Das, was HerrHagen vorschlägt, macht mein Code übrigens nicht. Da wird auch das erneut gestrichen, was schon gestrichen ist.

Jetzt gibt es nur noch 4 Java-Lösungen, die schneller sind ...

[HerrHagen]

@Graf Wasserrutsche: Das geht schon. Aber du solltest erstmal an anderer Stelle optimieren. Wenn ich das richtig seh überprüfst du jede zahl mit jeder zahl. Du musst die Zahlen aber nur auf Teilbarkeit mit Primzahlen überprüfen.
z.B. 2*2=4, alle Zahlen die durch 4 teilbar sind sind es auch durch 2. Also brauchst du nicht mit der 4 auf Teilbarkeit prüfen.

@numerix: hmm, schön. Da weiß ich jetzt, wo ich schneller sein kann... Hab nur leider wenig Zeit dafür. In 2-3 Wochen siehts vieleicht besser aus. Dann bist du dran mit deinen lepischen 0.35 sek.!

Weil ich gedanklich noch beim Code-Golf bin - hier auch mal ein Beitrag von mir (braucht auch nur 0.1s von 1 bis 100.000)

Code: Alles auswählen

primes = (3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,
          97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,
          181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,
          277,281,283,293,307,311,313)
def primefilter(start, stop):
    if start%2: start += 1
    primfilter = ' and '.join(["n%%%s" % p for p in primes])   
    return eval("[n for n in range(%s, %s, 2) if %s]" % (start, stop, primfilter))


start = int(raw_input("start"))
stop = int(raw_input("stop"))

from time import clock
t = clock()
primefilter(start, stop)
print clock() - t 

EDIT: Der obige Code ist unvollständig. Es müssen evtl. noch die vorberechneten Primzahlen zum Ergebnis hinzugefügt werden. Zudem funktioniert er nur bis 100.000.