Der Modulo-Operator

Der Modulo-Operator % steht für „Rest nach ganzzahliger Division“.
10 % 3 fragt also: Was bleibt über, wenn ich 10 durch 3 teile?

10 % 3 ergibt 1
15 % 4 ergibt 3
21 % 7 ergibt 0

Wenn das Ergebnis von x % y gleich 0 ist, bedeutet das: y ist ein Teiler von x!

Primzahlen

Primzahlen sind natürliche Zahlen größer als 1, die ausschließlich durch 1 und sich selbst ohne Rest teilbar sind.

Der Fundamentalsatz der Arithmetik

Jede natürliche Zahl größer als 1 lässt sich als Produkt von Primzahlen darstellen.
Diese Darstellung ist eindeutig.
4 = 2 * 2
12 = 2 * 2 * 3
100 = 2 * 2 * 5 * 5
17 = 17

Naiver Primzahl Test

def ist_primzahl(n):

    if n <= 1:
        return False
    
    for teiler in range(2, n):
        if n % teiler == 0:
            return False
    
    return True

Naiver Primzahl Test – kommentierte Fassung

def ist_primzahl(n):
 
    if n <= 1:
        print("n ist kleiner oder gleich 1!")
        return False
     
    for teiler in range(2, n):
        print("Teiler:", teiler)
        if n % teiler == 0:
            print(n, "ist durch", teiler, "teilbar!")
            print("Daher kann", n, "keine Primzahl sein.")
            return False
     
    print("Alle möglichen Teiler wurden untersucht und keiner gefunden!")
    print("Daher muss", n, "eine Primzahl sein.")
    return True

Die Anwendung sieht dann so aus:

ist_prim(7) ergibt True
ist_prim(12) ergibt False

Dieser Test funktioniert, ist aber sehr umständlich.

Eine erste Verbesserung besteht darin, dass wir nur bis zur Wurzel der Zahl n die Teiler suchen.

Begründung:
Wenn eine Zahl n keine Primzahl ist, muss sie mindestens zwei Faktoren a und b haben.
Nehmen wir also an, dass die Zahl n genau zwei Primfaktoren hat.
Wenn wir zudem annehmen, dass a und b größer als die Wurzel aus n sind, dann wäre das Produkt größer als n.
Das ist ein Widerspruch.
Es muss also zumindest einer der Primfaktoren kleiner als die Wurzel aus n sein.

Das nennen wir übrigens einen Beweis durch Widerspruch

1. Wir nehmen das Gegenteil von dem an, was wir beweisen wollen
2. Wir zeigen, dass diese Annahme zu einem logischen Widerspruch führt
3. Daraus folgt, dass die Annahme falsch sein muss
4. Also muss die ursprüngliche Behauptung wahr sein

Wurzeln ziehen in Python

Die Wurzel einer Zahl n ist die Zahl, die mit sich selbst multipliziert n ergibt:

√n × √n = n
In Python gibt es mehrere Möglichkeiten, die Wurzel zu berechnen:
Variante 1: Potenzierung mit 0.5

wurzel = n ** 0.5

Variante 2: Mit dem math-Modul

import math
wurzel = math.sqrt(n)

Variante 3: Ganzzahlige Wurzel (abgerundet)

import math
wurzel = math.isqrt(n)

Für unseren Primzahltest brauchen wir die ganzzahlige Wurzel, da wir nur ganze Zahlen als Teiler testen. Deshalb verwenden wir int(n ** 0.5).

Verbesserter Primzahl Test I – Nur bis zur Wurzel

def ist_primzahl(n):

    if n <= 1:
        return False

    wurzel_von_n = int(n ** 0.5)
    
    for teiler in range(2, wurzel_von_n + 1):
        if n % teiler == 0:
            return False
    
    return True

Verbesserter Primzahl Test II – Vielfache von 2 auslassen

Vielfache von 2 können keine Primzahlen sein.
Und bei range können wir eine Schrittweite einstellen.
Jetzt müssen wir nur noch die 2 gesondert behandeln:

def ist_primzahl(n):
 
    if n <= 1:
        return False
    
    if n % 2 == 0:
        return False
    
    wurzel_von_n = int(n ** 0.5)
     
    for teiler in range(3, wurzel_von_n + 1, 2):
        if n % teiler == 0:
            return False
     
    return True

Das Sieb des Erasthotenes

Wir lassen in der letzten Version unseres Primzahltests die Vielfachen von 2 weg. Warum nicht auch die Vielfachen von 3, 5, 6 und so weiter? Das ist die Idee hinter einem Verfahren, dass sich „Das Sieb des Erasthothenes“ nennt.

Das Sieb ist nur dann von Nutzen, wenn wir einen Zahlenbereich von 2 bis zu einer bestimmten Obergrenze nach Primzahlen durchsuchen wollen.

Es funktioniert folgendermaßen:
1. Erstelle eine Liste aller Zahlen von 0 bis zur Grenze und markiere zunächst alle als „prim“ (= True).
2. Markiere 0 und 1 als „nicht prim“ (= False).
3. Beginne mit der kleinsten Primzahl 2.
4. Streiche alle Vielfachen dieser Primzahl (außer der Zahl selbst), indem du sie als „nicht prim“ (= False) markierst.
5. Suche die nächste Zahl, die noch als „prim“ markiert ist.
6. Wiederhole Schritt 4 und 5, bis du die Wurzel der Grenze erreicht hast.
7. Alle Zahlen, die noch als „prim“ markiert sind, sind die gesuchten Primzahlen.

Das klingt komplizierter, als es ist. Hier ist eine Visualisierung:
LINK: Visualisierung des Sieb des Erasthothenes

Primzahlsuche mit dem Sieb des Erasthotenes

def primzahlen_bis(grenze):
    if grenze < 2:
        return []
    
    ist_prim = [True] * (grenze + 1)
    ist_prim[0] = ist_prim[1] = False
    
    wurzel_von_grenze = int(grenze ** 0.5)
    
    for zahl in range(2, wurzel_von_grenze + 1):
        if ist_prim[zahl]:
            for vielfaches in range(zahl * zahl, grenze + 1, zahl):
                ist_prim[vielfaches] = False
    
    return [zahl for zahl in range(grenze + 1) if ist_prim[zahl]]

Primzahlsuche mit dem Sieb des Erasthotenes – kommentierte Fassung

def primzahlen_bis(grenze):
    
    if grenze < 2:
        return []
     
    ist_prim = [True] * (grenze + 1)
    print("ist_prim am Anfang der Funktion:")
    print(ist_prim)
    
    ist_prim[0] = ist_prim[1] = False
    print("ist_prim im nächsten Schritt:")
    print(ist_prim)
     
    wurzel_von_grenze = int(grenze ** 0.5)
     
    for zahl in range(2, wurzel_von_grenze + 1):
        print("untersucht wird", zahl)
        if ist_prim[zahl]:
            print(zahl, "ist Primzahl")
            for vielfaches in range(zahl * zahl, grenze + 1, zahl):
                ist_prim[vielfaches] = False
                print(ist_prim)
     
    return [zahl for zahl in range(grenze + 1) if ist_prim[zahl]]

Echte Teiler

Echte Teiler sind alle Teiler einer Zahl außer der Zahl selbst.
Beispiel: Die Zahl 12 hat die Teiler 1, 2, 3, 4, 6, 12. Die echten Teiler sind 1, 2, 3, 4, 6.

def echte_teiler(n):
    if n <= 1:
        return []
    
    ergebnis = []
    for zahl in range(1, n):
        if n % zahl == 0:
            ergebnis.append(zahl)
    
    return ergebnis

Vollkommene Zahlen

Vollkommene Zahlen sind Zahlen, bei denen die Summe der echten Teiler die Zahl selbst ergibt.
Sie werden auch perfekte Zahlen genannt.

Wir können mit dem folgenden Programm nach vollkommenen Zahlen im Bereich bis 10000 suchen:

def echte_teiler(n):
    if n <= 1:
        return []
    
    ergebnis = []
    for zahl in range(1, n):
        if n % zahl == 0:
            ergebnis.append(zahl)
    
    return ergebnis

for n in range(1, 10000):
    echte_teiler_von_n = echte_teiler(n)
    summe = sum(echte_teiler_von_n)
    if summe == n:
        print(n)

def echte_teiler_schnell(n):
    if n <= 1:
        return {}
     
    ergebnis = {1}
    
    grenze = int(n**0.5)
    
    for potentieller_teiler in range(2, grenze+1):
        if n % potentieller_teiler == 0:
            ergebnis.add(potentieller_teiler)
            korrespondierender_teiler = n // potentieller_teiler
            ergebnis.add(korrespondierender_teiler)
    
    return ergebnis

Begriffe, offene Fragen, Stichworte

– Gibt es eine ungerade vollkommene Zahl?
– Gibt es unendlich viele vollkommene Zahlen?
– Primzahlzwillinge
– Gibt es unendlich viele Primzahlzwillinge
– Collatz-Vermutung
– Goldbachsche Vermutung