SPOJ - PRIME1 - Primzahlengenerator

Code-Stücke können hier veröffentlicht werden.
Benutzeravatar
HerrHagen
User
Beiträge: 430
Registriert: Freitag 6. Juni 2008, 19:07

Mittwoch 25. Februar 2009, 15:24

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

Mittwoch 25. Februar 2009, 16:04

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:

Mittwoch 25. Februar 2009, 16:20

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

Mittwoch 25. Februar 2009, 17:19

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

Mittwoch 25. Februar 2009, 17:44

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

Donnerstag 26. Februar 2009, 19:58

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

Donnerstag 26. Februar 2009, 20:28

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

Donnerstag 26. Februar 2009, 21:46

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

Dienstag 3. März 2009, 14:53

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

Dienstag 3. März 2009, 15:13

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

Freitag 6. März 2009, 10:22

numerix hat geschrieben: 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.
Kannst du mir erklären, wie du das genau meinst? Ich habe jetzt schon nach iterieren im allgemeinen gesucht, verstehe aber irgendwie nicht was damit explizit gemeint ist.

Und zum Code, pass ist weg und die 0 wird aus der Liste entfernt bzw. es wird eine neue Liste ohne die 0er erstellt. Anfangswerte m und m werden jetzt nicht mehr über die Funktion selbst übergeben.

Jetzt probiere ich gerade rum, wie ich es hinbekomme die geraden Zahlen zu überspringen. Scheint sehr einfach zu sein, aber der Schalter will sich bei mir nicht so einfach umlegen.

Code: Alles auswählen

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

    while curr_divider <= max_divider:  
        for i in range(0,len(sieve)):            
            if sieve[i] != 0:
                if int(sieve[i]) % curr_divider == 0 and int(sieve[i]) != curr_divider:
                    sieve[i] = 0      
        curr_divider += 1
    
    new = []
    for i in sieve:
        if i != 0:
            new.append(i)
    return new
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Freitag 6. März 2009, 11:05

``range`` hat ein drittes Argument, die Schrittweite. Wenn du als Schrittweite 2 angibst..
My god, it's full of CARs! | Leonidasvoice vs Modvoice
BlackJack

Freitag 6. März 2009, 11:36

@Graf Wasserrutsche: Und natürlich brauchst Du gerade `divider` auch nicht testen.

Warum steht da zweimal ``int(sieve)``? `sieve` enthält doch nur ganze Zahlen!?
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Freitag 6. März 2009, 12:25

BlackJack hat geschrieben:Warum steht da zweimal ``int(sieve)``? `sieve` enthält doch nur ganze Zahlen!?


Das hatte ich in meinem letzten Post auch schonmal gefragt - bis lang aber ohne Erfolg ... :cry:

@Graf Wasserrutsche: Bei aller Anerkennung für deine Ausdauer mehren sich bei mir doch allmählich die Zweifel, ob das eine Aufgabenstellung ist, die sich für dich in absehbarer Zeit lösen lässt, sofern du nicht ganze Code-Stücke geliefert bekommst.

Wie wäre es, wenn du dich zunächst an einer etwas einfacheren Aufgabe (kann ja auch was von SPOJ sein) versuchst und dann zu einem späteren Zeitpunkt - mit gestiegenen Fähigkeiten - nochmal zu PRIME1 zurück kehrst?
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

Sonntag 8. März 2009, 19:30

numerix hat geschrieben:
BlackJack hat geschrieben:Warum steht da zweimal ``int(sieve)``? `sieve` enthält doch nur ganze Zahlen!?


Das hatte ich in meinem letzten Post auch schonmal gefragt - bis lang aber ohne Erfolg ... :cry:

@Graf Wasserrutsche: Bei aller Anerkennung für deine Ausdauer mehren sich bei mir doch allmählich die Zweifel, ob das eine Aufgabenstellung ist, die sich für dich in absehbarer Zeit lösen lässt, sofern du nicht ganze Code-Stücke geliefert bekommst.

Wie wäre es, wenn du dich zunächst an einer etwas einfacheren Aufgabe (kann ja auch was von SPOJ sein) versuchst und dann zu einem späteren Zeitpunkt - mit gestiegenen Fähigkeiten - nochmal zu PRIME1 zurück kehrst?


Hm, ja, ich denke auch. Bin jetzt zwar schon einen Schritt weiter, brauche jetzt nur noch 0,01 Sekunden für die Berechnung der Basis-Primzahlen, aber der nächste Schritt wird wieder zu ner extremen Bastelei für mich. Also werde ich das mal ganz langsam angehen und mich erstmal an was anderem versuchen.

Trotz alledem hab ich schon ne Menge mit eurer Hilfe gelernt und wollt mich nochmal für die Mühe bedanken! Ich poste jetzt nochmal den Code der Primzahlenfunktion und werd mich bezüglich der Aufgabe dann in einiger Zeit bestimmt nochmal melden :)

Code: Alles auswählen

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

    while curr_divider <= max_divider:  
        for i in range(0,len(sieve)):            
            if sieve[i] != 0:
                if sieve[i] % curr_divider == 0 and sieve[i] != curr_divider:
                    sieve[i] = 0      
        curr_divider += 2
    
    new = []
    for i in sieve:
        if i != 0:
            new.append(i)
    return new
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Antworten