Primzahlen und das Faktorisierungsproblem

Primzahlen - Bausteine der natürliche Zahlen

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

Beispiele:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

Eine der wichtigsten Eigenschaften von Primzahlen ist, dass sie als Bausteine der natürlichen Zahlen angesehen werden können.

Satz: Jede natürliche Zahl lässt sich als Produkt von Primzahlen schreiben. Diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig.

Beispiel: Die Zahl 260 kann wie folgt mit Primzahlen aufgebaut werden:

260 = 2*2*5*13 = 22*5*13

Man nennt die Primzahlen, die in einer Produktdarstellung einer gegebenen Zahl vorkommen, auch Primfaktoren der Zahl.

Das Faktorisierungsproblem

Das Faktorisierungsproblem besteht darin, eine vorgegebene Zahl in ein Produkt aus Primfaktoren zu zerlegen.

Bei kleineren Zahlen kann man eine Primfaktorzerlegung oft direkt angeben. Bei größeren Zahlen sollte man systematisch vorgehen, um die Primfaktoren zu bestimmen. Bei noch größeren Zahlen ist es ratsam, die erforderlichen Berechnungen von einem Computer ausführen zu lassen - der kann das viel zuverlässiger und schneller.

Aufgabe 1

(a) Bei kleineren Zahlen kann man eine Primfaktorzerlegung oft direkt angeben. Bestimme eine Primfaktorzerlegung von n = 48 und n = 100. (Primzahlen werden grün markiert)

= × × × × × × ✅❌

(b) Bei größeren Zahlen sollte man systematisch vorgehen, um die Primfaktoren zu bestimmen. Bestimme eine Primfaktorzerlegung von n = 221 und n = 585.

(c) Entwickle zunächst einen Algorithmus zur Primfaktorzerlegung. Beschreibe in einem ersten Schritt in Worten das Verfahren, das du zur Primfaktorzerlegung von Zahlen benutzt. Beschreibe das Verfahren anschließend mit einem Struktogramm. Entwickle dann ein Programm zur Primfaktordarstellung. Hinweis: In Python bietet es sich an, eine Funktion primfaktoren(n) zu erstellen, die die Liste der Primfaktoren zurückgibt.