Implementierung des Primzahltestalgorithmus

Zur Orientierung

Ziel ist es, Funktionen für die im letzten Abschnitt betrachteten Primzahltestalgorithmen zu definieren. Vorab müssen aber einige Grundlagen gelegt werden.

Boolsche Funktionen

Eine boolsche Funktion ist eine Funktion, die als Ergebnis Wahrheitswerte (d.h. Datenobjekte vom Typ bool) liefert. Mehr über die Verarbeitung von Wahrheitswerten erfährst du im Abschnitt Wahrheitswerte und Bedingungen.

Beispiel:

def liefertImmerWahr(n):
    prim = True
    return prim

Aufgabe 1

(a) Teste die Funktion mit mehreren Testaufrufen.

>>> liefertImmerWahr(13)
...
>>> liefertImmerWahr(15)
...

(b) Wie würde man die Funktion liefertImmerFalsch definieren?

Fallunterscheidungen

Fallunterscheidungen werden in Python mit einer if-Anweisung implementiert. Mehr über Fallunterscheidungen erfährst du im Abschnitt Fallunterscheidungen.

Beispiel 1:

def istGerade(n):
    if n % 2 == 0:
        gerade = True
    else:
        gerade = False
    return gerade

Beispiel 2:

def istGerade(n):
    gerade = True
    if n % 2 == 1:
        gerade = False
    return gerade

Aufgabe 2

(a) Teste die beiden Implementierungen der Funktion istGerade mit geeigneten Testaufrufen. Worin unterscheiden sie sich im Verarbeitungsablauf?

(b) Entwickle analog die Funktionen istUngerade und istDurch5Teilbar.

Wiederholungen

Wiederholungen werden in Python mit einer while-Anweisung implementiert. Mehr über Wiederholungen erfährst du im Abschnitt Wiederholungen.

Beispiel:

def alleReste(n):
    k = 2
    while k < n:
        print(n%k)
        k = k+1
    return 'alles klar?'

Aufgabe 3

(a) Teste die Funktion alleReste mit geeigneten Testaufrufen. Beschreibe, was die Funktion leistet.

(b) Statt "alles klar?" soll die Funktion die Anzahl der Nullen liefern, die auf dem Bildschirm ausgegeben werden.

Implementierung der Primzahltestalgorithmen

Wir beginnen mit dem allereinfachsten Algorithmus.

ALGORITHMUS istPrimzahl:
    Übergabe: n    # natürliche Zahl
    prim = True
    k = 2
    SOLANGE k < n:
        WENN n % k == 0: 
            prim = False
        k = k+1
    Rückgabe: prim

Aufgabe 4

Entwickle passend zum Algorithmus eine Definition istPrimzahl und teste die Funktionsdefinition mit geeigneten Testaufrufen.

Aufgabe 5

Schaue dir nochmal die im letzten Abschnitt gezeigten Verbesserungen des Algorithmus an. Berücksichtige ebenfalls diese Verbesserungen in der Funktionsdefinition. Teste erneut.