Das deutsche Python-Forum

Hallo,
hab mich mal an der Implementierung in Python versucht.
Das ganze Skaliert nur sehr sehr schlecht, was natürlich auch am Algorithmus selbst liegen dürfte, aber vielleicht hängts auch am Code, drum hätt ich gerne ein paar Meinungen dazu

Code: Alles auswählen

def primeSieve(upperLimit):
    """
        Use sieve of Erastothenes to determine the primes till upperLimit.
        Returns a list
    """
    
#generate a dictionary of all odd numbers from 3 on, with default values of True
    primeCandidateDict = dict.fromkeys(xrange(3, upperLimit+1, 2), True)
    primeList = [2]     #2 is a prime for sure
    for prime in sorted(primeCandidateDict.keys()):
        #remove all multiples of prime
        if not primeCandidateDict[prime]: #Skip if prime's value is False
            continue
        for nonprime in xlrange(prime**2, upperLimit+1, prime):
            if nonprime in primeCandidateDict:
                primeCandidateDict[nonprime] = False
            else:
                continue
        primeList.append(prime)
    return primeList

€: Mittlerweile sogar recht flott

€²: xlrange() siehe hier, danke für das nützliche Snippet

Das hier:

Code: Alles auswählen

    primeCandidates = [x for x in range(3,upperLimit+1) if x % 2]
    primeCandidateDict = zip(primeCandidates, (len(primeCandidates) * [True]))
    primeCandidateDict = dict(primeCandidateDict)

würde man so schreiben:

Code: Alles auswählen

    primeCandidateDict = dict.fromkeys(xrange(3, upperLimit+1, 2), True)

"for prime in primeCandidateDict" durchläuft die Zahlen nur zufällig in aufsteigender Reihenfolge, das muss man also ändern.

Warum läuft "multiplicator" von 1 bis prime**2?
Sinnvoll wäre eine Schleife "for nonprime in xrange(prime**2, upperLimit+1, prime)".

Zieh noch mal die Forumssuche zu rate, da wirst du noch einige interessante Varianten finden.

Danke für die Kommentare birkenfeld, hab sie auch großteils berücksichtigt und den Code aktualisiert.

birkenfeld hat geschrieben: Warum läuft "multiplicator" von 1 bis prime**2?
Sinnvoll wäre eine Schleife "for nonprime in xrange(prime**2, upperLimit+1, prime)".

Die Schleife is falsch, das stimmt. Dein Ansatz ist allerdings falsch - wenn ich das richtig sehe, dass es immernoch die Multiplikation x * prime gibt.

Man kann mit "prime" selbst anfangen, da der Rest schon draussen ist. Allerdings darf man nicht "prime"-schrittig arbeiten.
Bsp: 3*3 -> 9, 3 * 5 -> 15
So sollte es ablaufen

Mit prime-schritten wirds aber zu 3², 3³, usw

@EyDu
Zur Primzahlbestimmung? Dann werd ich mal suchen ... zum Sieb hab ich leider nichts gefunden, hab allerdings nur in den Snippets gesucht.

Nein, die Multiplikation braucht man dann nicht mehr.

birkenfeld hat geschrieben:Nein, die Multiplikation braucht man dann nicht mehr.

Ahh Danke ... stand wohl ein wenig auf dem Schlauch.

Was mir allerdings aufgefallen ist: Bei großen Zahlen (>46.000) streikt Python mit der Fehlermeldung

Code: Alles auswählen

raceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "euler35.py", line 59, in primeSieve
    for nonprime in xrange(prime**2, upperLimit+1, prime):
OverflowError: long int too large to convert to int

cofi hat geschrieben:Was mir allerdings aufgefallen ist: Bei großen Zahlen (>46.000) streikt Python mit der Fehlermeldung
Code: Alles auswählen
OverflowError: long int too large to convert to int

Ist das eine aktuelle Python-Version?

Code: Alles auswählen

Python 2.5.2 (r252:60911, May 21 2008, 18:54:20)
[GCC 4.2.3 (Gentoo 4.2.3 p1.0)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>>

Ja, ``xrange`` kommt nicht mit longs zurecht. Dafür braucht es ``xlrange()`` - siehe Forumssuche.

Ah ok vielen Dank für den Hinweis. xlrange() is wirklich ne sehr nützliche Geschichte

Das deutsche Python-Forum

Primzahlbestimmung durch das Sieb des Eratosthenes

Primzahlbestimmung durch das Sieb des Eratosthenes