Primzahlbestimmung durch das Sieb des Eratosthenes

Code-Stücke können hier veröffentlicht werden.
Antworten
Benutzeravatar
cofi
Moderator
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Dienstag 10. Juni 2008, 14:08

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 :)
Zuletzt geändert von cofi am Mittwoch 11. Juni 2008, 19:36, insgesamt 4-mal geändert.
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Dienstag 10. Juni 2008, 14:37

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)".
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
EyDu
User
Beiträge: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Dienstag 10. Juni 2008, 15:42

Zieh noch mal die Forumssuche zu rate, da wirst du noch einige interessante Varianten finden.
Benutzeravatar
cofi
Moderator
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Dienstag 10. Juni 2008, 15:52

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.
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Dienstag 10. Juni 2008, 16:13

Nein, die Multiplikation braucht man dann nicht mehr.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Benutzeravatar
cofi
Moderator
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Dienstag 10. Juni 2008, 16:55

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
Benutzeravatar
mkesper
User
Beiträge: 919
Registriert: Montag 20. November 2006, 15:48
Wohnort: formerly known as mkallas
Kontaktdaten:

Mittwoch 11. Juni 2008, 13:27

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?
Benutzeravatar
cofi
Moderator
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Mittwoch 11. Juni 2008, 14:33

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.
>>>
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 11. Juni 2008, 16:51

Ja, ``xrange`` kommt nicht mit longs zurecht. Dafür braucht es ``xlrange()`` - siehe Forumssuche.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
cofi
Moderator
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Mittwoch 11. Juni 2008, 19:33

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