Die ersten 15 Primzahlen ausgeben

[Artur]

Tag liebes Forum

Ich versuche folgendes Programm zu schreiben,

Schreiben Sie ein Programm, welches die ersten 15 Primzahlen errechnet.
Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler,
nämlich der Zahl 1 und sich selbst.

Die Anzahl der Primzahlen wird bei mir noch über die range der zu prüfenden Zahlen bestimmt, kann als nicht sagen "Gib mir die ersten 15 Primzahlen aus."

Code: Alles auswählen

print "Wie viele Primzahlen sollen von 0 ausgehend ausgegeben werden? "
Anzahl=raw_input("Anzahl: ")
for n in range(2, 10):
    for x in range(2, n):
        if n % x == 0:          #modulo -> 8 % 3 = REST: 2      (2/3)
            break
    else:
        print n, 'ist eine Primzahl'

Ausgabe:
Wie viele Primzahlen sollen von 0 ausgehend ausgegeben werden? 
Anzahl: 15
2 ist eine Primzahl
3 ist eine Primzahl
5 ist eine Primzahl
7 ist eine Primzahl

Hat einer von euch eine Idee wie ich die ersten 15 Primzahlen über eine raw_input-Abfrage oder eben ohne Abfrage ausgeben kann ohne dabei die range zu verändern? (zb. range(1000))
Danke im Voraus.
LG

[BlackJack]

@Artur: Du lässt `n` nicht von 1 bis irgend einen festen Wert laufen, sondern bis „unendlich“, zum Beispiel mit `itertools.count()`, und merkst Dir wie viele Primzahlen Du schon gefunden hast. Wenn es 15 sind, brichst Du die Schleife ab.

Effizienter wäre es nicht immer durch alle Zahlen von 2 bis n-1 zu teilen, sondern durch die bisher schon gefundenen Primzahlen.

[problembär]

@Artur: Du lässt `n` nicht von 1 bis irgend einen festen Wert laufen, sondern bis „unendlich“, zum Beispiel mit `itertools.count()`

Was spricht gegen 'while True:' ?

[pillmuncher]

itertools.count()

Was spricht gegen 'while True:' ?

Mal sehen:

Code: Alles auswählen

from itertools import count
for n in count(2):
    """ do stuff with n """

# --8<--------8<--------8<--------8<--------8<--------8<--------8<--------8<--

n = 2
while True:
    """ do stuff with n """
    n += 1

Die erste Version gefällt mir deutlich besser. Dir nicht?

[problembär]

itertools.count()

Was spricht gegen 'while True:' ?

Mal sehen:

Code: Alles auswählen

from itertools import count
for n in count(2):
    """ do stuff with n """

# --8<--------8<--------8<--------8<--------8<--------8<--------8<--------8<--

n = 2
while True:
    """ do stuff with n """
    n += 1

Die erste Version gefällt mir deutlich besser. Dir nicht?

Ehrlich gesagt, mag' ich die zweite wirklich lieber. Schönes, klares, built-in-Python. Aber das ist Geschmackssache.

[pillmuncher]

Code: Alles auswählen

from itertools import count
for n in count(2):
    """ do stuff with n """

# --8<--------8<--------8<--------8<--------8<--------8<--------8<--------8<--

n = 2
while True:
    """ do stuff with n """
    n += 1

Die itertools.count()-Version ist einfacher, weil sie nicht verlangt, dass man eine Variable initialisiert, und sie dann an einer bestimmten Stelle ändert. "bestimmte Stelle" heißt: an nicht beliebiger Stelle. Das hier zB. bedeutet etwas anderes:

Code: Alles auswählen

n = 2
while True:
    n += 1
    """ do stuff with n """

aber das hier dasselbe wie die ursprüngliche Version:

Code: Alles auswählen

n = 1
while True:
    n += 1
    """ do stuff with n """

und alle drei Versionen unterscheiden sich hiervon:

Code: Alles auswählen

n = 1
while True:
    n += 1
    """ do stuff with n """
    n += 1

Die itertools.count()-Version ist in diesem Sinne einfacher: es gibt weniger Möglichkeiten, etwas verkehrt zu machen. Sie ist auch übersichtlicher: durch die Verwendung von n als loop-Variable entfällt die Initialisierung und durch die Verwendung von count() wird n nacheinander an jede einzelne einer beliebig langen Folge ganzer Zahlen gebunden - ohne weiteres Zutun. Das steht dabei alles übersichtlich in einer kurzen Zeile, statt verteilt an drei verschiedenen Stellen im Code. Der Code innerhalb des Loops besteht dann nur noch aus dem Test auf Primheit, der Verwaltung der gefundenen Primzahlen und dem Test auf die Abbruchbedingung. Man spart sich die Verwaltung der Zähler/Steuer-Variable. Außerdem ist die Denkrichtung weniger prozedural. Statt zu fragen: "was muss ich alles tun, um eine Folge ganzer Zahlen zu berechnen?" - Initialisieren, hochzählen - fragt man gar nichts, sondern nimmt die Bibliotheksfunktion, die genau diese Folge ausspuckt. Alles, was ich nicht selber programmieren muss, ist gesparte Zeit, und, wie oben schon gesagt, eine ausgeschlossene Fehlerquelle. Und Select Isn't Broken, was ich von meinem selbstgezimmerten Code leider nicht immer behaupten kann.

[Artur]

Es wäre doch ne Lösung, wenn ich nach dem 15. Durchlauf der While-Schleife den Vorgang abbreche oder? Ist es möglich nach der 15. Schleife eine break-Funktion einzubauen?
Das wäre sicher nicht die "beste" Lösung aber immerhin eine Lösung.

[Hyperion]

Ja klar ist das möglich - auch wenn `break` keine Funktion ist...

Aber was spricht denn gegen die vorgeschlagene Lösung mit `itertools.count`?

[Artur]

Sry, für meine Unwissenheit.. aber ich kann mit den Lösungsvorschlägen nichts anfangen. Ich habe so meine Probleme mit Python und fürchte, dass ich es nicht verstehen werde, bevor mir nicht jemand die komplette Lösung für die Aufgabe mit itertools hinklatscht, was ja auch wieder dumm ist. Ich versuche die tutorials für die Befehle zu lesen aber kann sie nicht auf die Aufgabe anwenden :/

[Hyperion]

Um eine Schleife abzubrechen ist die Funktionsweise von `itertools.count` letztlich irrelevant! Du hattest ja `break` schon in den Raum geworfen - bau Dir doch mal eine Test-Schleife, die bis 100 zählt und die Du nach dem 10. Durchlauf verlassen willst. Anschließend ersetzt Du die 100 durch `itertools.count` und bist einen Schritt weiter.

Zudem willst Du ja nicht nach x Durchgängen abbrechen, sondern nach x gefundenen Primzahlen Aber das wirst Du dann auch noch rausfinden; ist ja nicht schwer, die Bedingung dann umzuformulieren.

[Artur]

Wie verlasse ich denn eine Schleife nach dem 10 Durchlauf ? Steht das irgendwo im tut?

[Hyperion]

Wie verlasse ich denn eine Schleife nach dem 10 Durchlauf ? Steht das irgendwo im tut?

Ja, Kapitel 4.4 - "break and continue Statements, and else Clauses on Loops". Wie oft fiel das Statement `break` hier eigentlich schon - Du hast es sogar selber genannt!

[Artur]

Da steht wie man eine while-Schleife abbricht aber da steht nicht wie man eine while-Schleife nach dem zehnten Durchlauf abbricht. Sry wenn ich mich grad blöd anstelle '-'

[Hyperion]

Da steht wie man eine while-Schleife abbricht aber da steht nicht wie man eine while-Schleife nach dem zehnten Durchlauf abbricht. Sry wenn ich mich grad blöd anstelle '-'

Eigentlich steht da sogar nur, wie man eine `for`-Schleife abbricht - immerhin hast Du den Transfer zu `while` geschafft. Guck Dir doch mal den Kontext an, in dem `break` da steht... dann kommst Du sicher drauf, wie man das umsetzen kann

[Artur]

Ich probiere rum, aber das einzige was ich bisher hinbekommen hab, ist mithilfe noch einer for-Schleife die Wiederholung des gesamten Zählvorgangs zu vervielfachen, es wird also 15 mal von Wert 2 bis Wert 10 Primzahlen gezählt. Ich will ja aber die Anzahl der ausgegebenen zahlen auf 15 setzen bzw die Schleife nach der 15. Ausgabe abbrechen. Mein Laptop hat keinen Saft mehr, muss kurz heimlaufen.

[Hyperion]

Ich habe Dir doch den Tipp gegeben, das ganze erst einmal Schritt für Schritt aufzubauen! Wieso machst Du augenscheinlich schon wieder mit dem Primzahltest rum, wenn Du doch erst einmal das Problem lösen willst, eine Schleife unter einer bestimmten Bedingung abzubrechen?

Man programmiert Stück für Stück, nicht alles auf einmal!

Also, eine Schleife, die bis 100 zählt:

Code: Alles auswählen

for index in range(100):
    print(index)

Wenn ich die Schleife beim 10. Durchlauf verlassen will, muss ich also irgend wie das `break`-Statement hinschreiben:

Code: Alles auswählen

In [67]: for index in range(100):
   ....:         print(index)
   ....:         break
   ....:     
0

Mist! Nach dem ersten Durchlauf ist Schluss. Logisch, da `break` ohne Bedingung angelaufen wird. Die Bedingung ist ja, dass `index` den Wert 10 erreicht hat. Beim Wort Bedingung sollte es auch bei Dir "schrillen" -> `if`!!!

Aha, wir müssen also eine Bedingung formulieren, die prüft, ob `index == 10` ist. Wenn ja, dann soll die Schleife abgebrochen werden:

Code: Alles auswählen

In [68]: for index in range(100):
   ....:     print(index)
   ....:     if index == 10:
   ....:         break
   ....:         
0
1
2
3
4
5
6
7
8
9
10

Im Teil der Doku, auf den ich Dich verwiesen hatte, steht übrigens auch eine Bedingung mit `if` als Kopf des Blocks, in dem dann `break` aus der Schleife aussteigt. Wäre das nicht selber zu erarbeiten gewesen?

So weit so gut.

Für die Berechnung von Primzahlen wissen wir aber nicht, wie weit wir zählen müssen. Also können wir `range` nicht nutzen. Doof! Aber BlackJack hatte ja mal was von `itertools.count` erwähnt. Also flux in die Doku gucken und sehen was das Teil macht:

itertools.count(start=0, step=1)

Make an iterator that returns evenly spaced values starting with n. Often used as an argument to imap() to generate consecutive data points. Also, used with izip() to add sequence numbers. Equivalent to:

Code: Alles auswählen

    def count(start=0, step=1):
        # count(10) --> 10 11 12 13 14 ...
        # count(2.5, 0.5) -> 2.5 3.0 3.5 ...
        n = start
        while True:
            yield n
            n += step

When counting with floating point numbers, better accuracy can sometimes be achieved by substituting multiplicative code such as: (start + step * i for i in count()).

Mit anderen Worten zählt `count` von einem bestimmten Startwert ab bis ins Unendliche (theoretisch). Wir können damit also alle Zahlen Schritt für Schritt erzeugen, ohne vorher (wie bei `range`) die letzte Zahl zu kennen, die wir untersuchen müssen.

Schreiben wir das Snippet aus [68] einfach mal mit `count`:

Code: Alles auswählen

In [69]: from itertools import count

In [70]: for index in count():
   ....:     print(index)
   ....:     if index == 10:
   ....:         break
   ....:         
0
1
2
...

Klappt also ganz einfach.

Du brauchst nun noch eine Funktion `is_prime`, die für einen übergebenen Wert prüft, ob es sich um eine Primzahl handelt. Wenn ja hängst Du diese an die Liste der gefundenen Primzahlen an und prüfst, ob diese Liste schon 15 Einträge hat. Wenn ja, musst Du dann die Schleife via `break` abbrechen.

[Artur]

Also erst mal ein großes Danke an alle, besonders an Hyperion ^.^ . Ich hoffe du gehst jetzt nicht in die Luft, wenn ich dir sage, dass ich das was du dahin geschrieben hast noch nie gesehen hab und auch keine Ahnung habe wie ich die is_prime-Funktion schreibe. Ich finde irgendwie keine Struktur in Python. Ich sehe nur die unzähligen Befehle des Programms und denke bei jedem neuen Befehl "Wie benutzt man das jetzt richtig in Kombination mit dem". Und auch durch stundenlanges Ausprobieren komme ich nicht weiter. Ich hoffe irgendwann in der Zukunft macht es klick und alles ist auf ein Mal ganz einfach :/. Funktionen sind doch sowas wie Variablen, in die man auch Befehle und mehr verpacken kann oder? Wenn du mir sagst ich soll eine Funktion schreiben, die prüfen soll, ob es eine Primzahl ist oder nicht, fällt mir nur ein

Code: Alles auswählen

for n in range(2, 10):
    for x in range(2, n):
        if n % x == 0:          
            break
    else:
        print n, 'ist eine Primzahl'

in eine Funktion zu stopfen '-' was sicher nicht richtig ist. Die Zeilen hab ich im inet gefunden, weil ich nicht wusste, wie man auf Primzahl prüft und ehrlich gesagt verstehe ich immer noch nicht wie man mit mehreren Werten, die sich ändern arbeiten kann. Tut mir echt leid

[Artur]

Also Hyperion, ich hab versucht das itertools count irgendwie mit einer Primzahlprüfung zu kombinieren aber es kam nichts bei raus, bitte reg dich nicht auf

[problembär]

@Artur: Tja, deshalb ist es nach meiner bescheidenen Meinung ja auch besser, erstmal die grundlegen Konstruktionen gebrauchen zu lernen, später kann man sich dann immer noch Sonderfunktionen aus Modulen (wie itertools) holen, wenn man sie denn wirklich braucht (siehe die Diskussion mit pillmuncher oben).
In Python gibt es z.B. dieses "while", das auf eine Bedingung prüft:

Code: Alles auswählen

a = 1
while a == 1:
    print "a ist (immer noch) 1."

Wie Du siehst, läuft die Schleife unendlich.

Bedingungen werden nun in Python zu einer Aussage "True" oder "False" ausgewertet, so im interaktiven Modus:

Code: Alles auswählen

>>> a = 1
>>> a == 1
True

Deshalb kann man, wenn man eine unendliche Schleife haben will, am besten:

Code: Alles auswählen

while True:
    print "Immer True."

schreiben. So, das kombinierst Du dann noch mit einem Zähler und dem break-Statement, damit die Schleife dann doch irgendwann abgebrochen wird:

Code: Alles auswählen

x = 0
while True:
    print "x = " + str(x) + "."
    x += 1
    if x == 10:
        break
print "Schleife beendet."

Alles klar soweit?

[Artur]

Sag meinem Dozenten, dass man erst mal die Grundlagen lernen sollte. 1 Aufgabe pro Woche muss drin sein. Die ersten 2 waren pipifax, hab mir alles notiert was in der Vorlesung gesagt wurde. Bei der 3. war man dann aufgeschmissen, weil auf einmal Zeug kam, was man noch nie vorher gesehen/besprochen hat. Wenn ich nicht von Anfang an gut mitgemacht hätte, würde ich mich nicht so aufregen, darüber, dass jetzt gar nix klappt