Alle Primzahlen bis t ausgeben lassen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
zsanzhar
User
Beiträge: 19
Registriert: Samstag 17. Februar 2018, 21:28

Hallo,
könnte mir jemand helfen?
Ich muss alle Primzahlen bis t ausgeben lassen, aber mein programm gibt einige keine Primzahlen aus. Wo könnte mein Fehler sein?

Code: Alles auswählen

def allePrim(t):
    for i in range(2, t):
        for j in range(2, i):
            if i % j == 0:
                break
            print(i)
print(allePrim(40))
Vielen Dank
Sirius3
User
Beiträge: 17712
Registriert: Sonntag 21. Oktober 2012, 17:20

Beschreib doch mal, wie Dein Algorithmus funktionieren sollte und was Du jeweils ausgibst.
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

zsanzhar hat geschrieben: Sonntag 8. Juli 2018, 09:24 Ich muss alle Primzahlen bis t ausgeben lassen, aber mein programm gibt einige keine Primzahlen aus. Wo könnte mein Fehler sein?
Der Algorithmus ist der Fehler :)
Schau dir mal das Sieb des Eratosthenes an (https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes)

(Man kann mit deinen Code in der Form richtige Ergebnisse bekommen, indem man für die innere Schleife eine For-Else Schleife verwendet und 'print(i)' dort unterbringt. Allerdings sind For-Else Schleifen in Python eher ein Kuriosum und meistens gibt es einen gängigeren Weg, der ohne auskommt. )
zsanzhar
User
Beiträge: 19
Registriert: Samstag 17. Februar 2018, 21:28

Sirius3 hat geschrieben: Sonntag 8. Juli 2018, 09:45 Beschreib doch mal, wie Dein Algorithmus funktionieren sollte und was Du jeweils ausgibst.
es läuft für -for Schleife i von 2 bis t, da ich von 2 bis t alle Prims ausgeben will. Ich habe dann noch innere for schleife für teiler von 2 bis i-1 aufgebaut. Und überprüfe ob i mod j == 0 ist, wenn ja wird abgebrochen und soll die nächste i testen. wenn das trifft, muss es ausgegeben werden. :(
zsanzhar
User
Beiträge: 19
Registriert: Samstag 17. Februar 2018, 21:28

nezzcarth hat geschrieben: Sonntag 8. Juli 2018, 09:50
zsanzhar hat geschrieben: Sonntag 8. Juli 2018, 09:24 Ich muss alle Primzahlen bis t ausgeben lassen, aber mein programm gibt einige keine Primzahlen aus. Wo könnte mein Fehler sein?
Der Algorithmus ist der Fehler :)
Schau dir mal das Sieb des Eratosthenes an (https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes)

(Man kann mit deinen Code in der Form richtige Ergebnisse bekommen, indem man für die innere Schleife eine For-Else Schleife verwendet und 'print(i)' dort unterbringt. Allerdings sind For-Else Schleifen in Python eher ein Kuriosum und meistens gibt es einen gängigeren Weg, der ohne auskommt. )
ich habe mir angeschaut, aber habe nicht ganz verstanden. :(
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

Also wenn ich deinen Code ausführen lasse, wird das hier ausgegeben:

Code: Alles auswählen

3 5 5 5 7 7 7 7 7 9 11 11 11 11 11 11 11 11 11 13 13 13 13 13 13 13 13 13 13 13 15 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 19 19 19
19 19 19 19 19 19 19 19 19 19 19 19 19 19 21 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 25 25 25 27 29 29 29 29 29
 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
  31 31 31 31 31 31 33 35 35 35 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 39 None
So, da sind jede Menge Primzahlen, aber auch nicht Primzahlen dabei, zB 15 , 25, 33 und am Ende steht da ein None.

Fangen wir mit dem Ende an, in der Funktion gibts du die Zahlen per Print() aus (schlecht) und rufst dann die Funktion mit print() auf.
Eine jede Funktion liefert None zurück wenn ihr nicht per return ein anderer Rückgabewert zugewiesen wird.
Also aus dem print(allePrim(40)) wird ein allePrim(40), dann ist das None weg.

Für jede Zahl i von 2 bis t durchläuft deine innere Schleife die Teiler von 2 bis i, das ist schlecht.
Teste zuerst ob die Zahl durch 2 teilbar ist, wenn ja ist sie keine Primzahl,
des Weiteren reicht es bis zur Wurzel der Zahl i zu testen, alle Tests danach sind überflüssig, also for j in range(3, int(sqrt(i)+1)):

Dann überprüfst du, ob die Zahl i ganzzahlig durch den Teiler j teilbar ist, wenn ja, brichst du die innere Schleife per break ab,
aber das trifft ja auch nicht zu und in dem Fall gibst du jeweils per print(i) die Zahl aus.

Ich würde den Primzahl-Test in eine Funktion auslagern, die Wahr oder Falsch liefert.
Die Funktion allePrim() erzeugt dann eine Liste mit allen Primzahlen im Bereich 2 bis t
Mit einer for-Schleife kannst du dann alle Elemente dieser Liste ausgeben lassen.
Jetzt musst du dir nur noch die Funktion is_prime() überlegen

Code: Alles auswählen

def is_prime(number):
    return False, falls number keine Primzahl
    return True, falls number eine Primzahl ist

def allePrim(t):
    return [i for i in range(2, t) if is_prime(i)]

for zahl in allePrim(200):
    print(zahl)
Edit: für sqrt() musst du math importieren, und dann mit math.sqrt() aufrufen
Suche mal nach der Funktion all(), was die so macht, könnte hilfreich sein
Ich bin Pazifist und greife niemanden an, auch nicht mit Worten.
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

@zsanzhar:
Mal zur Verdeutlichung; denn du warst eigentlich (für den 'naiven' Algorithmus) schon fast da:

Code: Alles auswählen

def iter_primes(t):
    for i in range(2, t):
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            # edit: Klammer entfernt.
            yield i
print(list(iter_primes(40)))
Wenn du größere Zahlen als 40 nimmst, wirst es aber irgendwann eng, da der Algorithmus nicht sehr effizient ist. 'allePrim' ist außerdem ein ungünstiger Namen. Erstens würde man in Python eher 'alle_prim' schreiben, zweitens würde ich erwarten, dass sie dann nur einen Wahrheitswert zurück gibt.

Wo hakt es denn bei dem Verständnis des Siebverfahrens?
Zuletzt geändert von nezzcarth am Sonntag 8. Juli 2018, 12:29, insgesamt 1-mal geändert.
Sirius3
User
Beiträge: 17712
Registriert: Sonntag 21. Oktober 2012, 17:20

@zsanzhar: die Beschreibung ist sehr unpräzise:
zsanzhar hat geschrieben:wenn das trifft, muss es ausgegeben werden.
was zur Folge hat, dass das Programm auch sehr unpräzise Primzahlen ausgibt. Versuche das Problem und die Lösung so exakt wie möglich zu formulieren. Versuche auch das Problem in mehre Schritte aufzuteilen, also wie testet man eine einzelne Zahl ob sie prim ist und wie macht man das mit mehreren.

@nezzcarth: danke, dass Du die Hausaufgaben von anderen löst, auch wenn Generatoren wohl noch etwas zu fortgeschritten sind. `yield` ist keine Funktion, die Klammern um das `i` also unsinnig.

@ThomasL: mit Optimierungen kann man dann Anfangen, wenn das Problem gelöst ist. Im relevanten Fall ist sowieso die Benutzung eines Siebs die Optimierung.
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

@Sirius3: Dass ich beim Ersetzen von print durch yield die Klammer vergessen habe, ist richtig. Danke für den Hinweis. Ansonsten sehe ich ehrlich gesagt wenig Anlass für Maßregelung. :) Wenn jemand eine fast funktionierende Lösung zeigt und es nur an Details hakt, kann man denke ich auch auf die Sprünge helfen; insbesondere dann, wenn klar darauf hingewiesen wird, dass die Lösung defizitär ist und ohnehin nicht verwendet werden sollte.
Benutzeravatar
__blackjack__
User
Beiträge: 13006
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@nezzcarth: Doch die Lösung sollte verwendet werden, nämlich als Abgabe für die Hausaufgabe. :-) Hausaufgaben fordern ja öfter mal Sachen die man in echt so nicht machen würde.

Hier mal eine reale Lösung:

Code: Alles auswählen

from sympy import primerange


def main():
    for prime in primerange(0, 40):
        print(prime)


if __name__ == '__main__':
    main()
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
zsanzhar
User
Beiträge: 19
Registriert: Samstag 17. Februar 2018, 21:28

Danke sehr für deine ausführliche Erklärung:).
Ich glaube, ich habe es hinbekommen.

Code: Alles auswählen

def is_prim(number):
    teiler = 2
    while math.sqrt(number) >= teiler:
        if number % teiler == 0:
            return False
        teiler += 1
    return True
print(is_prim(2))



def alle_Prim(t):
    k = []
    for i in range(2, t-1):
        if is_prim(i):
            k.append(i)
    return k
print(alle_Prim(50))
Liebe Grüße,
Janyl
Sirius3
User
Beiträge: 17712
Registriert: Sonntag 21. Oktober 2012, 17:20

@zsanzhar: warum hast Du jetzt die for-Schleife durch eine while-Schleife ersetzt? Und warum suchst Du nur Primzahlen bis 48?
zsanzhar
User
Beiträge: 19
Registriert: Samstag 17. Februar 2018, 21:28

nezzcarth hat geschrieben: Sonntag 8. Juli 2018, 12:09 @zsanzhar:
Mal zur Verdeutlichung; denn du warst eigentlich (für den 'naiven' Algorithmus) schon fast da:

Code: Alles auswählen

def iter_primes(t):
    for i in range(2, t):
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            # edit: Klammer entfernt.
            yield i
print(list(iter_primes(40)))
Dankeschön :), mmmh aber was macht yield?
zsanzhar
User
Beiträge: 19
Registriert: Samstag 17. Februar 2018, 21:28

Sirius3 hat geschrieben: Sonntag 8. Juli 2018, 12:49 @zsanzhar: warum hast Du jetzt die for-Schleife durch eine while-Schleife ersetzt? Und warum suchst Du nur Primzahlen bis 48?
Mm, while und for Schleifen sind, ja, gleich, oder? ich suche nicht nur bis 48. ich suche bis t, für t kann ich ja beliebige Zahl eingeben.
zsanzhar
User
Beiträge: 19
Registriert: Samstag 17. Februar 2018, 21:28

__blackjack__ hat geschrieben: Sonntag 8. Juli 2018, 12:44 @nezzcarth: Doch die Lösung sollte verwendet werden, nämlich als Abgabe für die Hausaufgabe. :-) Hausaufgaben fordern ja öfter mal Sachen die man in echt so nicht machen würde.

Hier mal eine reale Lösung:

Code: Alles auswählen

from sympy import primerange


def main():
    for prime in primerange(0, 40):
        print(prime)


if __name__ == '__main__':
    main()
:-D, sowas darf ich ja nicht benutzen
Benutzeravatar
__blackjack__
User
Beiträge: 13006
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@zsanzhar: Wenn ``for``- und ``while``-Schleifen gleich wären, bräuchte man ja nur eines von beiden. Es hat einen Grund das es beide gibt.

``for``-Schleifen sind dafür da über Werte zu iterieren für die man vor der Schleife schon einen Ausdruck schreiben könnte um die zu erzeugen, und das kann man wenn man ganze Zahlen von einem Start- bis zu einem Endewert (exklusive) braucht ganz einfach mit `range()` machen. Ohne das man vor und irgendwo in der Schleife noch irgend etwas zusätzliches machen muss, wie das bei ``while`` der Fall ist. ``while`` ist da schwerer zu verstehen, weil sich der Code für Initialisierung, Abbruchbedingung, und aktualisieren des oder der Werte die für die Abbruchbedingung herangezogen werden, über den Code verteilt sind, während das bei der ``for``-Schleife alles hinter dem ``in`` steht. Und das auch kompakter.

Edit: Und Du suchst nur bis 48 weil Du zwar 50 angibst, dann aber nur die Zahlen 2 bis 48 testest:

Code: Alles auswählen

In [17]: print(list(range(2, 50 - 1)))
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43,
44, 45, 46, 47, 48]
Zuletzt geändert von __blackjack__ am Sonntag 8. Juli 2018, 13:26, insgesamt 1-mal geändert.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Sirius3
User
Beiträge: 17712
Registriert: Sonntag 21. Oktober 2012, 17:20

@zsanzhar: in diesem Fall ist aber eine for-Schleife deutlich besser, weil von vornherein klar ist,bis zu welchem Maximalwert die Schleife durchlaufen wird und einfach immer nur ein Zähler hochgezählt wird.

Im Beispiel t=50 mag es bis 48 gehen, für andere t eben bis zu einem anderen Wert, aber niemals bis t. Das ist halt falsch.
Antworten