Primzahlen finden! Euler 3

[seriöserName]

Ich habe einen Code geschrieben, welcher die Primzahlen, in einem bestimmten Bereich finden soll. Allerdings teilt mein Programm anscheinend nicht immer richtig. Das erste Problem lässt sich schon bei 16 finden.
Im Folgenden seht ihr den Code + Das was es ausgespuckt hat.

Code: Alles auswählen

def euler3():

    prim_lst = [2]
    div = 3
    while div <= 100:
        for x in prim_lst:
            
            if div % x == 0:
                print(div, "in if. not append. Devisible by %d " % (x))
                div +=1
                
        else:
            print(div,"in else. append. Last divisor %d " % (x))
            prim_lst.append(div)
            div+=1
            
        
    print(prim_lst)
    print(len(prim_lst))

        

     
euler3()

(13, 'in else. append. Last divisor 11 ')
(14, 'in if. not append. Devisible by 2 ')
(15, 'in if. not append. Devisible by 3 ')
(16, 'in else. append. Last divisor 13 ')
(17, 'in else. append. Last divisor 16 ')
(18, 'in if. not append. Devisible by 2 ')

Liste + Länge der Liste:

[2, 3, 5, 7, 11, 13, 16, 17, 19, 23, 27, 29, 31, 35, 37, 41, 43, 47, 50, 53, 59, 61, 65, 67, 71, 73, 77, 79, 83, 87, 89, 95, 97, 101]

34

Ich bin ratlos, da er anscheinend 2 ebenfalls ausprobiert hat, aber aus irgendeinem Grund nicht in das if statement gegangen ist. :K
Bitte um eure Hilfe und danke im voraus.

[BlackJack]

@seriöserName: So wie es dort steht wird wird der ``else``-Zweig *immer* am Ende der ``for``-Schleife ausgführt. Ein ``else`` zum ``for`` wird ausgeführt wenn die Schleife nicht durch ``break`` verlassen wurde. Da dort nirgends eine ``break``-Anweisung vorkommt…

Anmerkungen zum Quelltext: Besser keine kryptischen Namen und/oder Abkürzungen und keine konkreten Grunddatentypen in Namen kodieren. `prim_lst` würde besser `primes` heissen. `div` vielleicht besser `candidate` weil es ein Kandidat für eine Primzahl ist, der geprüft werden soll. Und `x` ist eine Primzahl, also `prime`.

Wenn man sich die Ausgabe anschaut, dann sieht man, dass Du Python 2.x verwendest. Dort ist ``print`` eine Anweisung und Du gibst da *einen* Wert aus, nämlich ein Tupel. Also entweder die Klammern weglassen oder durch den entsprechenden Import aus dem `__future__`-Modul ``print`` tatsächlich zu einer Funktion machen.

Dein Ansatz ist übrigens nicht besonders effizient um eine Primfaktorzerlegung zu machen erst alle möglichen Primzahlen zu berechnen. Da fallen mehr Rechenoperationen an, als wenn man gleich anfangen würde die eigentliche Zahl die man zerlegen möchte auf Teiler zu testen und zu zerkleinern.

Die Aufgabe hatte mich dazu bewegt ein Primzahlzerlegungsprogramm für grosse Zahlen für den C64 zu schreiben. Da habe ich auch noch eine Primzahlerzeugung drin, die nicht sein müsste. Muss ich irgend wann mal rauswerfen.

Edit: Muss ich doch nicht rauswerfen, denn ich hatte mir vorhin nur den Quelltext vom Hauptprogramm angeschaut. Die Primzahl”erzeugung” in dem Programm besteht aus einer statisch vorberechneten Bitmap von einem Sieve-Algorithmus für alle Primzahlen bis 2¹⁶. Das schränkt die Primfaktorgrösse die man damit finden kann natürlich ein, aber da ist man dann auch an der Grenze des Sinnvollen für einen 8-Bit-Rechner mit ca. 1Mhz Prozessortak. Und die Euler-Aufgabe lässt sich damit lösen.

[bb1898]

Zusätzlicher Rat: viele Euler-Aufgaben drehen sich um Primzahlen. Es lohnt sich, gleich von Anfang an ein bisschen Zeit in die entsprechenden Informationen zu stecken und sich vielleicht ein entsprechendes Modul zu schreiben, das man immer wieder verwenden kann. Erstes Stichwort: Sieb des Eratosthenes. Außerdem gibt es gerade zu den frühen Aufgaben oft kurze Übersichtsartikel mit Hinweisen zu einfachen und besseren Algorithmen - an die kommt man zwar erst nach dem Lösen der jeweiligen Aufgabe, aber sie sind nützlich fürs Weiterkommen. Und vielleicht willst Du Deine Lösungen ja auch hinterher noch verbessern.

Und im übrigen ist einerseits Python eine sehr geeignete Sprache für solche Aufgaben - allein schon die Leichtigkeit, mit der man große Zahlen verwenden kann - andererseits sind die Aufgaben gut, um zumindest Teile der Sprache besser kennenzulernen und einzuüben.

[pixewakb]

Programmieren lernen - setz Dich auf den Rücken von Riesen und schau in die Welt.

Riese = http://www.sympy.org/en/index.html

Welt = Project Euler

Ich denke, dass Du dort fertige Möglichkeiten findest, Deine Probleme zu lösen...