Das deutsche Python-Forum

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.

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

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

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

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

@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

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

jerch hat geschrieben: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.