eidp-klausuraufgaben/loops/primes/README.md

Primzahlen

is_prime

Eine Primzahl ist eine Zahl die nur durch sich selbst und eins teilbar ist. Implementieren Sie die Funktion is_prime(n: int) -> bool welche

• True wenn n größer als 1 ist und eine Primzahl
• sonst False

next_prime

Nun schreiben wir eine Funktion next_prime die eine Zahl n nimmt und uns die nächst größere Primzahl zurückgibt.

• Sie können diese sowohl iterativ also auch rekursiv lösen
• Es müssen keine weiteren Randbedingungen beachtet werden

prime_factorize

Eine beliebiges aber festes n \in \mathbb{N}_2 kann entweder eine Primzahl sein oder eine Zahl welche man in ein Produkt aus Primzahlen zerlegen kann. Dieses Verfahren nennt man Primfaktorzerlegen.

Als kleines Beispiel kann man 20 als Produkt 2 \cdot 2 \cdot 5 darstellen. Dieses ist vor allem eindeutig und man kann für jeder Zahl ein solches Produkt finden.

Schreiben Sie nun folgende Funktion prime_factorize(n: int) -> list[int] welche

• für Zahlen n < 2 eine leere Liste zurückgibt ([])
• für Zahlen n die Prim sind einfach eine Liste mit der Zahl n zurückgibt ([n])
• sonst für alle weiteren eine Liste mit den Primfaktoren zurückgibt ([p1, p2, p3, ...] mit p1 * p2 * p3 * ... = n)

Tipp: Sie können hierfür die Funktionen is_prime und next_prime verwenden

Hier gehts zu den Lösungen