[Python-de] Primzahlenberechnung, Effiziente Speicherung

[Gregor Lingl]

Andreas Jung schrieb:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 26.01.2009 12:26 Uhr, Robert Heumüller wrote:
>   
>> Hallo zusammen!
>>
>> Da dies mein erster Kontakt mit einer Mailingliste ist, möchte ich euch
>> bitten mir nachzusehen, dass ich mit der Arbeitsweise noch nicht ganz
>> vertraut bin.
>> Nun zu meiner Frage, bzw. zu meinem Problem:
>>     
>
> Dein Problem ist eher der Algorithmus. Warum verwendet Du nicht einen
> Standardalgorithmus wie Sieb des Erathostenes?
>
> http://www.little-idiot.de/python/x388.html
>   
Na ja, ganz so einfach ist es auch wieder nicht. Der in diesem Link 
gezeigte Algorithmus dürfte auch
nicht (signifikant) schneller sein als Roberts. Aber ein kleine Änderung

def PrimesLE(limit):
    Primes = [2]
    counter = 3
    while counter <= limit :
        for KnownPrime in Primes:
            if counter % KnownPrime == 0:
                break
            elif KnownPrime*KnownPrime > counter:
                Primes.append(counter)
                break
        counter = counter + 2
    return Primes

macht ihn gleich um einen Faktor 30 schneller (für limit = 100000).

Beste Grüße
Gregor
> Andreas
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (Darwin)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iEYEARECAAYFAkl9prkACgkQCJIWIbr9KYwlxACfRN9JXEMbjvbNPcf44PvYzy1V
> 6S8AmwYrPOqEgAZdK6gbMEpgA6WLZZVO
> =MuNW
> -----END PGP SIGNATURE-----
>   
> _______________________________________________
> python-de maillist  -  python-de at python.net
> http://python.net/mailman/listinfo/python-de
>