Problem mit einer Aufgabe

[Rudolph]

Guten Tag,
ich bin ein Schüler und habe Informatikunterricht. Bis jetzt hatte ich nie Probleme damit, die Aufgaben meines Lehrers zu lösen. Heute aber haben wir eine ganz schön schwere Aufgabe bekommen. Ich erwarte nicht das ihr mir die Lösungen gebt und das will ich auch nicht! Ich hoffe nur ihr könnt mir ein paar Tipps zur Lösung dieser Aufgabe geben.

Die Aufgabe lautet:
Schreibe ein Programm .. ,das den Anwender auffordert eine natürliche Zahl einzugeben und dann alle Primzahlen bis zu dieser Zahl ermittelt und in einer Liste speichert. Dazu soll eine Funktion .. verwendet werden, die überprüft, ob die Zahl eine Primzahl ist oder nicht und einen entsprechenden Wahrheitswert zurück liefert.

Leider habe ich keine Ahnung wie ich die Zahl auf primzahligkeit(bin mir nicht sicher ob es dieses Wort gibt) überprüfe bzw. die anderen Zahlen bis zu dieser Zahl.

Meine einzige Grundidee ist, dass die anderen Zahlen mit einer Zählschleife überprüft werden müssten.

Ich hoffe ihr könnt mir weiterhelfen


MfG

Rudolph

[EyDu]

Hallo und willkommen im Forum!

Am besten ist es wohl, wenn du die Formussuche mal nach dem Begriff "Primzahl" bemühst, dann wirst du mindestens einen längeren Thread dazu finden. Ansonsten liefert dir Wikipedia bereits eine Menge an Ansätzen, sogar in Form von Code.

[Rudolph]

Also hier in Forum finde ich nur die 3 Themen (Sage - Primzahl;Primzahl;Zahl kleiner machen durch ZAHL % PRIMZAHL). In Wikipedia finde ich zwar schon etwas, jedoch Hilft mir das nicht, weil es nicht zur Aufgabenstellung passt.

[darktrym]

Du hast eine Liste aller gefunden Primzahlen bis n.
Also müsste jede weitere Zahl(n+1), sofern sie eine Primzahl ist, nicht teilbar sein durch Elemente aus dieser Liste.

[cofi]

Stichwort: Sieb des Erastothenes.

Wie du testest ob eine Zahl prim ist, ergibt sich aus der Definition: Sie ist nur durch sich selbst und 1 restlos teilbar. Die naive Loesung ist also eine Schleife in einer Schleife zu benutzen. Mit ein paar Optimierungen ist man dann schnell an erwaehntem Algorithmus.

[Rudolph]

Du hast eine Liste aller gefunden Primzahlen bis n.
Also müsste jede weitere Zahl(n+1), sofern sie eine Primzahl ist, nicht teilbar sein durch Elemente aus dieser Liste.

Die Liste habe ich nicht.
Den zweiten Satz versteh ich nicht ganz. Sofern eine Zahl eine Primzahl ist ist sie doch sowieso nicht durch eine andere Primzahl bzw. Zahl außer 1 und sich selbst teilbar.

[Rudolph]

Stichwort: Sieb des Erastothenes.

Wie du testest ob eine Zahl prim ist, ergibt sich aus der Definition: Sie ist nur durch sich selbst und 1 restlos teilbar. Die naive Loesung ist also eine Schleife in einer Schleife zu benutzen. Mit ein paar Optimierungen ist man dann schnell an erwaehntem Algorithmus.

Also die Idee mit einer Schleife in einer Schleife hat mir schonmal weitergeholfen.
Bis jetzt habe ich das hier: (noch falsch)

Code: Alles auswählen

primliste = [2]
    teiler = 1
    for zahl in range(2,n//2):
            while teiler <= zahl // 2:
                teiler = teiler + 1
                if zahl % teiler == 0:
                    continue
                primliste.append(zahl)

Hier ist auch eine Sache die ich nicht ganz verstehe(habe die zahl 16 genommen als n) am Ende sind 2 ; 4 und 6 in der Liste. Ich versteh nicht wie die 4 und die 6 reinkommen. z. B. die 4 müsste direkt von der Schleife und der Zeilen

Code: Alles auswählen

if zahl % teiler == 0:
                    continue

rausgefiltert werden, da ja nur die 2 als Teiler erlaubt wird und die Schleife bei der 3 aufhört und 4 / 2 nunmal keinen Rest hat müsste die letzte Zeile ja übersprungen worden sein..

[darktrym]

Okay,
du hast eine Liste mit einem Element 2.

Nun testet du ob:
3 - kein Teiler, also prim, ab in Liste(2,3)
4 - hat 2 als Teiler, entsorgen
5 - kein Teiler, ab in Liste(2,3,5)
6 - Teiler 2, entsorgen
7 - kein Teiler, ab in Liste(2,3,5,7)
8 - Teiler 2, entsorgen
9 - Teiler 3, entsorgen
...

Du siehst man muss eigentlich nur jedes 2. Element untersuchen und bis maximal Wurzel n gehen.
Der Algorithmus ist primitiv (und ineffient).

[Rudolph]

Okay,
du hast eine Liste mit einem Element 2.

Nun testet du ob:
3 - kein Teiler, also prim, ab in Liste(2,3)
4 - hat 2 als Teiler, entsorgen
5 - kein Teiler, ab in Liste(2,3,5)
6 - Teiler 2, entsorgen
7 - kein Teiler, ab in Liste(2,3,5,7)
8 - Teiler 2, entsorgen
9 - Teiler 3, entsorgen
...

Du siehst man muss eigentlich nur jedes 2. Element untersuchen und bis maximal Wurzel n gehen.
Der Algorithmus ist primitiv (und ineffient).

Okay jetzt bin ich hier angekommen:

Code: Alles auswählen

primliste = [2]
    teiler = 1
    for zahl in range(3,n//2):
            while teiler <= zahl / 2:
                teiler = teiler + 2
                if zahl % teiler == 0:
                    break
                primliste.append(zahl)
    return primliste

Leider wird der Schleife kein weiteres Element hinzugefügt(außer die 6), also ist mindestens noch ein Fehler drin, aber ich seh ihn nicht..
Und ich weiß nicht wie die 6 da reinkommt.. 6 % 3 == 0 soweit ich weiß und dann müsste die Schleife für die 6 ja fertig sein.

[darktrym]

Du musst schon prüfen ob die zu untersuchende Zahl auch ja keinen Teiler hat in der Liste deiner bereits gefunden Primzahlen.
Im Prinzip zwei in sich geschachtelte for-Schleifen, die äußere iteriert über alle Zahlen, die innere über die Elemente aus primliste. Die Abbruchbedingung hast du bereits richtig erkannt.

[webspider]

Passend eingestreute print-Anweisungen sind ebenfalls eine primitive, aber sehr hilfreiche Debuggingmethode.

[Rudolph]

Du musst schon prüfen ob die zu untersuchende Zahl auch ja keinen Teiler hat in der Liste deiner bereits gefunden Primzahlen.
Im Prinzip zwei in sich geschachtelte for-Schleifen, die äußere iteriert über alle Zahlen, die innere über die Elemente aus primliste. Die Abbruchbedingung hast du bereits richtig erkannt.

Ich weiß jetzt nicht genau wie du das meinst..
Hab es so umgesetzt, aber das ist leider auch falsch:

Code: Alles auswählen

    primliste = [2]
    teiler = 1
    for zahl in range(3,n//2):
            while teiler <= zahl / 2:
                teiler = teiler + 2
                for listenteiler in primliste:
                    if zahl % listenteiler == 0:
                        break
                if zahl % teiler == 0:
                    break
                primliste.append(zahl)
    return primliste

Könntest du es nochmal anders erklären?

[Rudolph]

Passend eingestreute print-Anweisungen sind ebenfalls eine primitive, aber sehr hilfreiche Debuggingmethode.

Ja okay. Aber ich weiß nicht wo ich die hinsetzten soll und bin mir sicher es gibt auch eine andere Lösung.

[darktrym]

Code: Alles auswählen

primes = [2]
last = int(input("number: "))
for number in xrange(3, last, 2):
    (?1)
    for test in primes:  
        if number % test  == 0:
            (?2)
            break
    if (?3):
        primes.append(number)
print primes     

Ich habs so gelöst, nun musst du nur noch die Fragezeichen klären

[Rudolph]

Code: Alles auswählen

primes = [2]
last = int(input("number: "))
for number in xrange(3, last, 2):
    (?1)
    for test in primes:  
        if number % test  == 0:
            (?2)
            break
    if (?3):
        primes.append(number)
print primes     

Ich habs so gelöst, nun musst du nur noch die Fragezeichen klären

Okay dafür danke ich dir schonmal. Aber 2 Fragen hätt ich noch:
1. Kann man statt "xrange" einfach "range" hinschreiben? Da wir xrange noch nicht gelernt haben, darf ich es auch nicht nutzen.
2. Ich weiß nicht was in der ersten Lücke(?1) fehlt.. Also auf den Inhalt der anderen beiden Lücken komm ich bestimmt noch, aber die erste Lücke hätt ich freigelassen.

[darktrym]

1.) Klar doch.
2.) Ersetze mal die Fragezeichen durch print Anweisungen. Und probier's mal mit Eingabe von 30.

[Rudolph]

1.) Klar doch.
2.) Ersetze mal die Fragezeichen durch print Anweisungen. Und probier's mal mit Eingabe von 30.

Alle 3? Also auch das mit if?
Und was soll denn ausgegeben werden?
Und was bringt das wenn ich etwas ausgebe?

[EyDu]

Du sollst dir die Zwischenergebnisse ausgeben lassen, so siehst du, was du falsch gemacht hast.

Zu dem if: for-Schleifen kann man noch einen else-Block anfügen, welcher genau dann ausgeführt wird, wenn man die Schleife nicht mit break verlassen hat. Jetzt kannst du dir ja mal überlegen, was das mit deinem Fall zu tun hat.

[Rudolph]

Du sollst dir die Zwischenergebnisse ausgeben lassen, so siehst du, was du falsch gemacht hast.

Zu dem if: for-Schleifen kann man noch einen else-Block anfügen, welcher genau dann ausgeführt wird, wenn man die Schleife nicht mit break verlassen hat. Jetzt kannst du dir ja mal überlegen, was das mit deinem Fall zu tun hat.

Also irgendwie bin ich zu blöd dafür..
Also wenn ich die Zwischenergebnisse ausgeben soll muss es doch so aussehen oder?:

Code: Alles auswählen

    primliste = [2]
    for zahl in range(3,n,2):
        for teiler in primliste:
            print(primliste)
            if zahl % teiler == 0:
                print(primliste)
                break
        if print(primliste):
            primliste.append(zahL)
        return primliste

[EyDu]

Prinzipiell schon, dein Code wirft aber wahrscheinlich einen NameError. Und noch zwei Dinge, die mir aufgefallen sind: Du solltest dir angewöhnen nicht gleich wegen jedem Kleinkram zu fragen, wie willst du sonst etwas lernen? Sieben Minuten von einem Hinweis bis zum abschicken einer Antwort, machen keine fünf Minuten Arbeit aus. Wie soll man da etwas vernünftig testen? Und zweites: wenn etwas nicht funktioniert, dann schreibe was nicht funktioniert, was du für eine Eingabe machst, was du erwartest, was raus kommt, wie die Fehlermeldung lautet und poste den gesamten Traceback. Warum soll man Fehler raten, wenn du die Antwort quasi schon zur Hand hast.