SPOJ - PRIME1 - Primzahlengenerator

Code-Stücke können hier veröffentlicht werden.
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

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.
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

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]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

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

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:

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
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Wird Psyco denn überhaupt akzeptiert von SPOJ?
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

Bei Adding Reversed Numbers (ADDREV) hat es funktioniert.
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

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:

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!
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Benutzeravatar
HerrHagen
User
Beiträge: 430
Registriert: Freitag 6. Juni 2008, 19:07

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

HerrHagen hat geschrieben: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
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

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
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

numerix hat geschrieben:
HerrHagen hat geschrieben: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 ... :D
Benutzeravatar
HerrHagen
User
Beiträge: 430
Registriert: Freitag 6. Juni 2008, 19:07

@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... :wink: 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.
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

So, ich schließe jetzt von Grund auf mal alle Vielfachen von 2 aus und reduziere die Zeit damit auf ca. 0.95 Sekunden für die Primzahlen bis 100000. Bei 900000 bis 1000000 sieht es dann total anders aus, da sind es dann 2.6 Sekunden.

Wäre die Lösung mit meinem jetzigen Code-Ansatz machbar, oder sollte ich von Grund auf neu anfangen? Ich komme aktuell nicht darauf alle Vielfachen der schon gefundenen Primzahlen zu streichen und auf die Art und Weise mit der ich es mit diesem Code realisiert habe wird dieser um einiges langsamer.

Bisher habe ich es so ausprobiert eine Liste mit allen Vielfachen zu erstellen und diese abzuarbeiten, dann habe ich versucht die Vielfachen von curr_divider zu removen, erhalte aber dann ja einen List-IndexError, weil die Anzahl der Elemente nicht mehr stimmt. Wenn ich hierzu die Stelle mit index() ermittle dauert der Code schonmal locker 0.5 Sekunden länger. Hmpf.

Code: Alles auswählen

def sieve(m,n):
    sieve = range(m,n+1)
    
    max_divider = int(sqrt(n))/2
    curr_divider = 2

    if sieve[0] == 1:
        sieve[0] == 0

    while curr_divider <= max_divider:  
        for i in range(0,len(sieve)):            
            if curr_divider > 2 and curr_divider % 2 == 0:
                pass
            else:
                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
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Graf Wasserrutsche hat geschrieben:Wäre die Lösung mit meinem jetzigen Code-Ansatz machbar
Nein. Jedenfalls nicht innerhalb der Laufzeitbegrenzung.

Du sagst, du schließt die geraden Zahlen von vornherein aus. "Von vornherein" sieht aber anders aus als das, was du machst. Du schließt sie eben nicht "von vornherein" aus, sondern durchläufst alle Zahlen und prüfst jede Zahl dann erst auf gerade/ungerade. Und ein "pass" braucht man hier ganz sicher auch nicht.

Ich glaube, dass du am falschen Ende herumdoktorst. Statt immer nur auf die großen Zahlen zu blicken, fang mit den kleinen an. Aber das habe ich ja schon mehr als einmal gepostet ...

Papier, Bleistift und ein Ausschnitt aus den Primzahlen bis 100. Und dann mit den Zahlen spielen und drüber nachdenken ... das könnte ein richtiger Ansatz werden. :)
BlackJack

@Graf Wasserrutsche: Schau Dir doch mal das Sieb des Eratosthenes an. Das was Du da machst ist nämlich nicht die typische Implementierung. In der wird nicht jede Zahl zum aussieben genommen, also Dein ``current_divider += 1``, sondern nur solche von denen man bereits weiss, dass sie Primzahlen sind.
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

So, ich habe mich jetzt im Zuge des Testens und der Optimierung auf die Zahlen bis 100 beschränkt, im Zuge der Gesamtlösung habe ich es natürlich auch mit großen Zahlen ausprobiert und bin wieder auf das Geschwindigkeitsproblem gestoßen, aber dazu später. Vielleicht ist es ja möglich die Schritte einzelnd zu dokumentieren.

Zu allererst berechne ich einfach alle Primzahlen von 2 bis zu der Wurzel von 1000000000, weil man, wenn ich es richtig verstanden habe, nur diese Primzahlen braucht um durch diese die nötigen Vielfachen zu errechnen, welche gestrichen werden müssen. Ist das so schon mal korrekt?

Dann erstelle ich mit Hilfe der Werte m und n eine Liste der Zahlen von m bis n. Von den bereits ausgerechneten Primzahlen brauche ich nur die Primzahlen von 2 bis zur Wurzel des Maximalwertes n. Ist das so korrekt?

Jetzt zu dem meiner Vermutung nach großen Geschwindigkeitsproblem. Ich durchlaufe die Primzahlen bis zur Wurzel des Maximalwertes und streiche die Vielfachen, in dem ich durch die Liste aller Zahlen laufe und teste ob diese Zahlen durch die Primzahlen geteilt den Wert 0 ergeben. Wenn ja, dann ersetzte ich die jeweiligen Zahlen durch eine 0.

Gibt es hierzu irgendeine andere Möglichkeit das zu bewerkstelligen? Ich wüsste nicht wie man sonst Vielfache streichen sollte.

Diese Lösung läuft jetzt im Vergleich zu meinen ersten Versuchen relativ schnell und auch Zahlen von 1 bis 100000 werden in bis zu 0.4 Sekunden (die erste Berechnung der Primzahlen mit einbegriffen) ausgerechnet. In höheren Regionen gibt es dann natürlich wieder Zeitprobleme.

Hier mein aktueller Versuch:

Code: Alles auswählen

from math import sqrt 
from time import clock

import psyco
psyco.full()

def primes(m,n):
    sieve = range(m,n+1)
    
    max_divider = int(sqrt(n))/2
    curr_divider = 2
    
    sieve[1] = 0

    while curr_divider <= max_divider:  
        for i in range(0,len(sieve)):            
            if curr_divider > 2 and curr_divider % 2 == 0:
                pass
            else:
                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

def sieve(m,n):
    sieve = range(m,n+1)    
    maximum = int(sqrt(n))
   
    for i in range(2,maximum):
        if all_primes[i] != 0:
            for x in range(0,len(sieve)):
                if sieve[x] % all_primes[i] == 0:
                    sieve[x] = 0
    return sieve
    
c = clock()
all_primes = primes(0,int(sqrt(1000000000)))
sieve(1,100000)
print clock() - c
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Zunächst einmal finde ich es sehr anerkennenswert, dass du immer noch nicht aufgegeben hast, obwohl ich der Erfolg noch nicht eingestellt hat!
Graf Wasserrutsche hat geschrieben:Zu allererst berechne ich einfach alle Primzahlen von 2 bis zu der Wurzel von 1000000000, weil man, wenn ich es richtig verstanden habe, nur diese Primzahlen braucht um durch diese die nötigen Vielfachen zu errechnen, welche gestrichen werden müssen. Ist das so schon mal korrekt?
Ist korrekt. Aber so wie du es machst, noch nicht effizient genug. Ein paar Denkanstöße dazu:

Das "pass" muss weg - habe ich schonmal drauf hingewiesen. Überleg doch mal, wie du das gleiche ohne pass erreichen kannst.

Da du die Funktion primes nur dazu benutzen willst, dir einen Basissatz an Primzahlen zu erstellen, brauchst du keine Parameter; zumindest ist das m überflüssig.

Da du das ganze Sieb durchläufst, kannst du auch gleich über das Sieb iterieren anstatt eine neue Liste via range() zu erstellen und über diese zu laufen.

Die while-Schleife wird doppelt so oft durchlaufen wie nötig. Zu zählst in Einerschritten hoch, prüfst dann erstmal, ob die Zahl überhaupt ungerade ist und machst in dem Fall nichts. Warum überspringst du die geraden Zahlen nicht gleich?

Was soll int(sieve) bewirken?

Und schließlich: Du willst doch eine Liste aller Primzahlen erzeugen. Du erzeugst aber eine Liste, die so lange ist, dass sie ALLE Zahlen bis knapp 32.000 fassen könnte und irgendwo da drin befinden sich deine Primzahlen. Schmeiß die anderen Zahlen weg und erzeuge dir eine Liste, in der NUR noch die Primzahlen sind.

Wenn du das alles umsetzt, bist du schon ein Stück weiter.

Graf Wasserrutsche hat geschrieben:Dann erstelle ich mit Hilfe der Werte m und n eine Liste der Zahlen von m bis n. Von den bereits ausgerechneten Primzahlen brauche ich nur die Primzahlen von 2 bis zur Wurzel des Maximalwertes n. Ist das so korrekt?


Ja. Aber du solltest erstmal die primes()-Funktionen verbessern und dich dann wieder um das Sieb kümmern, dann das baut ja auf den erzeugten Primzahlen auf.
Antworten