Aufgabe 2: Rekursion 2 (Primfaktorzerlegung) Assignment

Jede Zahl kann in ein bis auf Reihenfolge eindeutiges Produkt von Primzahlen zerlegt werden. Diese Darstellung wird Primfaktorzerlegung genannt und ist in der Mathematik von elementarer Bedeutung (siehe auch: https://de.wikipedia.org/wiki/Primfaktorzerlegung). Zum Beispiel kann die Zahl 42 als Primfaktorzerlegung 42 = 2 · 3 · 7 geschrieben werden. 

1. Schreiben Sie ein Unterprogramm prime_factors(n), das die Primfaktorzerlegung einer Zahl rekursiv berechnet und in einer sortierten Liste zurück gibt. Beachten Sie, dass hierbei Primfaktoren auch mehrfach auftreten können ! 

2. Schreiben Sie ein Unterprogramm ggT(a, b), das den größten gemeinsamen Teiler von zwei Zahlen a und b zurück gibt. 

3. Schreiben Sie ein Unterprogramm kgV(a, b), das das kleinste gemeinsame Vielfache zweier Zahlen a und b zurück gibt. 

4. Schreiben Sie ein Unterprogramm proper_divisors(a), dem die Primfaktorzerlegung einer Zahl in Form einer Liste a übergeben wird (wie in Teilaufgabe 1 erzeugt), daraus alle (echten) Teiler der Zahl berechnet und sie in einer sortierten Liste zurück gibt. 

Hinweis: Der Head wird automatisch vor Ihren abgegebenen Code eingefügt, der Foot dahinter. Bitte kopieren Sie ihn nicht in Ihre Abgabe!

Scaffold Head

import sys # suppress users print commands _print = print print = lambda msg, *args, **kwargs: _print('#'+str(msg), *args, **kwargs)

Scaffold Foot

input_data = sys.stdin nums = [int(next(input_data)) for _ in range(3)] pairs = [eval(next(input_data)) for _ in range(3)] prims = [eval(next(input_data)) for _ in range(2)] # 2.1 for p in nums: _print(prime_factors(p)) # 2.2 for a, b in pairs: _print(int(ggT(a, b))) # 2.3 for a, b in pairs: _print(int(kgV(a, b))) # 2.4 for factors in prims: _print(proper_divisors(factors)) print = _print

Start time:

Fr 01 Dez 2017 15:13:13

End time:

Do 07 Dez 2017 14:00:29

General test timeout:

60.0 seconds

Tests

20728
42
36
(42, 16)
(14, 0)
(23424, 2352)
[2, 2, 2, 2591]
[2, 2, 3, 3]

# 2.1
[2, 2, 2, 2591]
[2, 3, 7]
[2, 2, 3, 3]
# 2.2
2
14
48
# 2.3
336
0
1147776
# 2.4
[1, 2, 4, 8, 2591, 5182, 10364]
[1, 2, 3, 4, 6, 9, 12, 18]