108 lines
2.9 KiB
Markdown
108 lines
2.9 KiB
Markdown
# Solution
|
|
|
|
## `is_prime`
|
|
|
|
Zunächst überprüfen wir alle Randbedingungen für `n < 2`
|
|
|
|
```python
|
|
if n < 2:
|
|
return False
|
|
```
|
|
|
|
wir wissen laut definition dass hier die Funktion zu `False` evaluieren soll.
|
|
|
|
|
|
Jetzt wollen wir durch alle Zahlen bis zu unserer Zahl `n` iterieren und schauen ob sich `n` noch anders teilen lässt
|
|
|
|
```python
|
|
for num in range(2, n):
|
|
if n % num == 0:
|
|
return False
|
|
```
|
|
|
|
Wenn `n` durch `num` teilbar ist können wir `False` zurückgeben, da `n` nicht nur durch sich selbst teilbar ist.
|
|
|
|
Jetzt geben wir noch `True` zurück wenn wir durch die For-Schleife iteriert sind und haben die Funktion.
|
|
|
|
```python
|
|
def is_prime(n: int) -> bool:
|
|
if n < 2:
|
|
return False
|
|
for num in range(2, n):
|
|
if n % num == 0:
|
|
return False
|
|
return True
|
|
```
|
|
|
|
Anmerkung: Wir müssen eigentlich nur alle Zahlen von $2$ bis $\lfloor n / 2 \rfloor$ so wie in der [Musterlösung](./primes.py). Warum?
|
|
|
|
<details>
|
|
<summary>Begründung:</summary>
|
|
Naja alle Zahlen größer als die Hälfte unserer zu testenen Zahl n sind keine Ganzzahligen Teiler außer unsere Zahl n selber. Betrachten wir 7, warum müssen wir nur bis 3 testen?
|
|
|
|
- 7 / 2 > 2
|
|
- 7 / 3 > 2
|
|
- 7 / 4 < 2
|
|
- ...
|
|
- 7 / 7 = 1
|
|
</details>
|
|
|
|
## `next_prime`
|
|
|
|
Wir inkrementieren solange `n` bis `is_prime` erfüllt ist und geben diesen Wert dann zurück.
|
|
|
|
Iterativ:
|
|
|
|
- wir speichern uns `n` zwischen und inkrementieren initial
|
|
- nun testen wir in einer `While`-Schleife `num` bis diese eine Primzahl ist und geben sie zurück
|
|
|
|
```python
|
|
num += 1
|
|
while not is_prime(num):
|
|
num += 1
|
|
return num
|
|
```
|
|
|
|
Rekursiv:
|
|
|
|
- Unsere Abbruchbedingung ist, dass `n + 1` eine Primzahl ist
|
|
- Ansonsten müssen wir rekursiv `n` inkrementieren bis wir eine Zahl erreichen die Prim ist
|
|
|
|
```python
|
|
if is_prime(n + 1):
|
|
return n + 1
|
|
else:
|
|
return next_prime(n + 1)
|
|
```
|
|
|
|
## `prime_factorize`
|
|
|
|
Zunächst definieren wir alle Variabeln die wir brauchen
|
|
|
|
```python
|
|
prime_factors: list[int] = [] # unsere Primfaktoren
|
|
num = n # damit wir n nicht verändern
|
|
prime = 2 # erste Primzahl
|
|
```
|
|
|
|
Nun müssen wir eigentlich nur noch solange `num` durch Primzahlen teilen bis `num == 1` ist.
|
|
Wichtig hierbei ist dass eine Primzahl mehrfach vorkommen kann, also müssen wir immer wieder bei `2` anfangen.
|
|
|
|
```python
|
|
while num > 1:
|
|
if num % prime == 0: # wir haben eine primzahl gefunden
|
|
prime_factors.append(prime)
|
|
num //= prime
|
|
prime = 2 # wichtig prime auf 2 zu setzen
|
|
# weil wir von vorne suchen müssen
|
|
else: # wenn wir keine passende Primzahl gefunden haben
|
|
prime = next_prime(prime) # dann springen wir zur nächsten
|
|
```
|
|
|
|
Und dann geben wir nur noch die liste `prime_factors` zurück. Diese ist
|
|
|
|
- für ungültige Eingaben `n <= 1` leer, da die Schleifenbedingung nie erfüllt ist.
|
|
- für Primzahlen `n` genau `[n]`, da Primzahlen nur durch sich selbst Teilbar sind
|
|
- oder alle Primfaktoren die also Produkt `n` ergeben
|
|
|