SPOJ - PRIME1 - Primzahlengenerator

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