Compute 10001. Prime Number (Project Euler)

[HarteWare]

Hallo zusammen,

ich habe versucht, das Problem 7 von Project Euler zu lösen. Nach mehreren Bugs, die ich beheben konnte, habe ich folgendes "Endprodukt":

Code: Alles auswählen

#!/usr/bin/env python3
# Output the Nth prime number

from Problem3 import isPrime  # isPrime function

def main():
    primes = [2]
    currNum = 3
    n = int(input("Compute Nth Prime Number: "))
    if n < 1:
        print("Error: n must be greater than 0\n")
        return
    while len(primes) < n:    
        if isPrime(currNum):
            primes.append(currNum)
        currNum += 2      # no even primes after 2
    print(str(n) + ". Prime Number:", primes[-1])

if __name__ == '__main__':
    main()

ein paar Beispiel Outputs:

Code: Alles auswählen

IN    OUT
----------
  1      2
  2      3
  3      5
 10     29
 50    191
100    377
999   3749

Für 10001 (wie es in der Aufgabe lautet) erhalte ich 37507, was mir als falsch angezeigt wird

Meine isPrime Funktion:

Code: Alles auswählen

def isPrime(n):
    primesUnder100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    if n <= 100:
        return n in primesUnder100
    else:
        if n % 2 == 0:
            return False
        elif n % 3 == 0:
            return False
        elif n % 5 == 0:
            return False
        else:
            for i in range(6, int(n ** 0.5), 6):
                if n % i == 0:
                    return False
        return True

Die Aufgabenstellung konkret nochmal:

Code: Alles auswählen

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?

Ich hoffe ihr könnt mich mal wieder auf meinen Fehler hinweisen, ich sitz mal wieder auf dem Schlauch.

[BlackJack]

@HarteWare: Deine Beispieltabelle ist ab 50 falsch, die 50. Primzahl ist 229. Dein `isPrime()` hat also sehr wahrscheinlich ein Problem. Erkläre die doch mal Schritt für Schritt. Wie kommen bestimmte "magische" Werte zustande die da einfach so literal im Quelltext stehen und was ist mit Randfällen.

[HarteWare]

Ich habe die Funktion abgeändert (nachdem ich einen kleinen Denkfehler hatte, dass ich es durch besagte magische Werte optimieren könnte).

Code: Alles auswählen

def isPrime(n):
    primesUnder100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    if n <= 100:
        return n in primesUnder100
    else:
        for i in range(2, int(n ** 0.5) + 1): 
            if n % i == 0:
                return False
    return True

Danke für den Hinweis.

Die Funktion stimmte eben leider nur für Primzahlen bis 100^^

[EyDu]

An deinem Code solltest du noch einiges verbessern. Als erstes solltest du dir PEP 8 anschauen und dich an die Standardschreibweisen von Bezeichnern gewöhnen. Statt "isPrime" also "is_prime", etc. Dann ist dein Code für andere besser lesbar.

Da es sich bei der Liste von Primzahlen um eine Konstante handelt, sollte diese außerhalb der Funktion definiert werden. Dann wird die Liste auch nur beim Programmstart erstellt und nicht bei jedem Aufruf der Funktion. Auch solltest du aus der Liste eine Menge machen, das Durchsuchen von Listen ist nämlich eine recht teure Aktion. Im Schlimmsten Fall müssen alle Elemente durchsucht werden. Bei einer Menge kann in konstanter Zeit entschieden werden, ob sich ein Element in der Menge befindet oder nicht.

Ein weiteres Problem ist, dass die 100 als Grenze magisch auftaucht. Wenn du die Liste mit Primzahlen veränderst, dann musst du immer daran denken, dass du auch die 100 änderst. Hier böte es sich an, einfach das größte Element der Primzahlenliste zu verwenden. Wenn n kleiner gleich dem größten Element ist, nur dann testest du die Liste.

Den Test gegen die Liste kannst du aber eigentlich immer durchführen, egal ob n>100 ist oder nicht. In Zeile 6 beginnst du dann einfach nicht bei 2, sonder irgendwo später. In diesem Beispiel bei 99. Damit kannst du dir einen Sonderfall sparen.

Wenn du schon auf Geschwindigkeit optimierst, dann solltest du auch deine for-Schleife in Zeile 6 verbessern. Es ist unnötig alle Zahlen von zwei an zu testen. Du kannst ganz einfach die Hälfte der Tests sparen, wenn du die zwei und alle *ungeraden* Zahlen ab drei testest. Falls du Python 2.x verwendest, könnte auch das "range" zu einem Problem werden, da eine Liste mit allen Elementen von Untergrenze bis Obergrenze erstellt werden. Im schlimmsten Fall erzeugst du also Millionen von Elementen, obwohl der Test bei der ersten Zahl fehlschlägt. Ggf. solltest du also xrange verwenden.

Die Schleife von Zeile 6 bis 8 kannst du noch etwas einfacher ausdrücken. Schau dir dazu mal Generatorausdrücke und die any- bzw. all-Funktionen an. Damit sparst du wieder einen Sonderfall.

Ansonsten solltest du dich mal hier im Forum umschauen, zu Primzahlen gibt es hier jede Menge interessanter Threads. Auch zu der von dir bearbeiteten Aufgabe.

[HarteWare]

Vielen Dank für die ausführliche Rückmeldung. Ich weiß sowas zu schätzen und habe mal versucht meinen Code zu verbessern.

Was ich noch nicht ganz verstehe, wieso ich nicht mehr bei 2 beginnen muss. In der For-Schleife teste ich ja, ob es einen Teiler von n gibt, der nicht 1 und nicht n ist. Wenn ich nun x Zahlen auslasse,
prüfe ich ja nicht ob diese Zahlen möglicherweise Teiler sind, daher könnten doch Zahlen als Primzahl durchgehen, die eigentlich nicht prim sind.
Also sagen wir ich iteriere ab 99, vielleicht ist die Zahl durch 3 teilbar (nicht selbst 3) und damit lasse ich die Zahl als prim durchgehen, obwohl sie keine ist, weil ich erst ab 99 überprüfe. Oder hab ich da was falsch verstanden?

Da ich python 3 benutze, ist bei mir range equivalent zu xrange in python 2, wenn ich das recht in Erinnerung habe.

Das ganze mit den "Sonderfällen" hab ich jetzt auch nicht ganz verstehen können. Also z.B. ich spare mir einen Sonderfall, wenn ich nicht bei 2, sondern später beginne (siehe auch weiter oben)

Ich will nun versuchen diese Generatoren und any/all zu verwenden. Bin ich mit dem Ansatz richtig, dass ich mithilfe eines geeigneten Generatorausdrucks ein "iterable" erzeugen kann, dass ich any/all als Parameter übergeben kann?

Soweit bin ich mal gekommen:

Code: Alles auswählen

# Wäre doch geschickt, diese Menge bei gefundener Primzahl zu erweitern...
PRIMES = {
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
        31, 37, 41, 43, 47, 53, 59, 61, 67,
        71, 73, 79, 83, 89, 97                    
    }

def is_prime(n):
    if not n in PRIMES:
        tests = (n % i == 0 for i in range(2, int(n**0.5) + 1))
        if any(tests):
            return False
    return True

Ob das so in dieser Form tatsächlich einfacher/schöner ist, lässt sich drüber streiten. Vielleicht ist meine Anwendung aber auch einfach nur unpassend...
Ich bin mir jetzt nicht sicher, ob man Mengen Konstanten auch upper case schreiben soll, aber ich habs jetzt mal gemacht.

[Sirius3]

@HarteWare: was soll denn jetzt die if-Abfrage bewirken? Dass Du alle Zahlen<100, die keine Primzahlen sind nochmals testest, dass sie wirklich keine sind? Die Vorberechnung der ersten paar Primzahlen ist sowieso kaum eine Optimierung. Das macht Deinen Algorithmus nur unnötig komplizierter. Die Wurzel aus 100 ist 10, Du mußt also maximal 5 Zahlen testen. Dafür lohnt sich meiner Meinung nach der Aufwand eine Lookuptabelle zu erzeugen, nicht. Das mit dem Generatorausdruck passt so.

[BlackJack]

@HarteWare: `tests` brauchst Du nicht, Du kannst den Ausdruck auch gleich als Argument an `any()` übergeben. Und da der Aufruf dieser Funktion entweder `True` oder `False` liefert, kann man sich die beiden ``if``\s auch sehr leicht einsparen. Etwas kürzer wird es dann noch wenn man `all()` statt `any()` verwendet und den Test umkehrt:

Code: Alles auswählen

def is_prime(n):
    return n in PRIMES or all(n % i != 0 for i in range(2, int(n**0.5) + 1))

[HarteWare]

@Sirius3 Naja ich dachte mir das so: Wenn die Primzahl keine bekannte Primzahl ist, dann schauen ob sich ein teiler ungleich 1 und der Zahl selbst finden lässt. Falls ja -> es ist keine. Sonst ist es eine.

Das mit dem Umdrehen der Abfrage und Nutzen von all() hatte ich mir auch schon überlegt, habs dann aber erstmal so gelassen.
Jedenfalls ist die Lösung inzwischen deutlich eleganter (die Tabelle wird in diesem Ausmaß wohl tatsächlich keinen nennenswerten Unterschied machen).
Außerdem hab ich ziemlich viel Neues gelernt (insbesondere das mit any()/all() etc.), und dafür macht man ja diese Aufgaben.

In dem Sinne, vielen Dank an alle, die dazu beigetragen haben

[Sirius3]

@HarteWare: zur Vollständigkeit. Falls Du tatsächlich in 6er-Schritten die Zahlen abtesten willst, mußt Du pro Schritt zwei Zahlen prüfen 6i+1 und 6i+5:

Code: Alles auswählen

def is_prime(n):
    return n>1 and ((n%2!=0 and n%3!=0 and all(n % i != 0 and n % (i+2) !=0 for i in range(5, int(n**0.5) + 1, 6))) or n==2 or n==3)

[HarteWare]

@Sirius3
Als erstes solltest du dir PEP 8 anschauen und dich an die maximale Zeilenlänge in einem Python Programm gewöhnen.

(ich hoffe das wird als Spaß verstanden!)