SPOJ - PRIME1 - Primzahlengenerator

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

[Graf Wasserrutsche]

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

[numerix]

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]

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

[numerix]

Zunächst einmal finde ich es sehr anerkennenswert, dass du immer noch nicht aufgegeben hast, obwohl ich der Erfolg noch nicht eingestellt hat!

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.

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]

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

[Leonidas]

``range`` hat ein drittes Argument, die Schrittweite. Wenn du als Schrittweite 2 angibst..

[BlackJack]

@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!?

[numerix]

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

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

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

@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

[derdon]

Wenn n und max_divider sowieso statische werte haben, dann kannst du denen auch gleich diese Werte direkt zuweisen (dir scheint Gescheindigkeit ja wichtig zu sein):

Code: Alles auswählen

n = 31622
sieve = range(1,n+1,2)
max_divider = 88
# ...

[jerch]

Hallo!
Ich war auch mal Primeln sieben und habs auf den 2. Platz geschafft, aber nur mit psychedelischem Turboknopf.

@nummerix:
Hut ab, Du hast da ziemlich die Nase vorn. Mit Turbo würdest Du sicher um die 0.20 wenn nicht gar drunter kommen. Mein Problem ist das obere Sieb, das ist mir nicht so richtig performant gelungen (ich hatte vorher ohne psyco 1.12). Vllt. packts mich nochmal und ich setze mich mit Papier und Bleistift hin wie Du das empfohlen hattest. Dein Abstand spricht jedenfalls Bände, mir fehlte da die zündende Algorithmus-Idee. Wäre mal interessant wie schnell Dein Verfahren in C/C++ ist.

Grüße, Jerch

[numerix]

Hallo!
Ich war auch mal Primeln sieben und habs auf den 2. Platz geschafft, aber nur mit psychedelischem Turboknopf.

@nummerix:
Hut ab, Du hast da ziemlich die Nase vorn. Mit Turbo würdest Du sicher um die 0.20 wenn nicht gar drunter kommen. Mein Problem ist das obere Sieb, das ist mir nicht so richtig performant gelungen (ich hatte vorher ohne psyco 1.12). Vllt. packts mich nochmal und ich setze mich mit Papier und Bleistift hin wie Du das empfohlen hattest. Dein Abstand spricht jedenfalls Bände, mir fehlte da die zündende Algorithmus-Idee.

Gratuliere!

Mein Algorithmus - jedenfalls, der, der aktuell noch die Pole-Position innehat - dürfte mit psyco (wenn überhaupt) nur unwesentlich schneller werden, weil er so optimiert ist, dass psyco da nichts oder wenig bringt. Aber das probiere ich erst aus, wenn es ohne psyco nicht mehr für Platz 1 reicht ...

Was meinen Algorithmus angeht, so ist der im Grunde ziemlich schlicht. Es gibt zwar modernere Siebverfahren (z.B. Sieb von Atkins), aber die habe ich nicht eingesetzt, sondern bin beim bewährten Eratothenes geblieben.

Das finde ich gerade das Faszinierende daran - und das war bisher bei fast allen SPOJ-Aufgaben so, mit denen ich mich beschäftigt habe: Die besten Lösungen waren meistens auch die schlankesten, jedenfalls dann, wenn ich auf psyco verzichtet habe.

[numerix]

Wenn jerch es aus Bescheidenheit nicht selbst tut, mach ich es mal:
Er ist der neue Primzahlkönig! Mit 0.25 s hat er das mit Abstand schnellste Python-Programm zur Lösung von PRIME1. GRATULATION!

Wir warten auf HerrHagen ...

[jerch]

Danke numerix

Du hast die Latte aber auch sehr hoch gehängt, zumal ohne psyco.