← RU Pythoncursus

Priemfactorontbinding

We gaan in deze opdracht een geheel getal ontbinden in zo klein mogelijke stukjes, die het oorspronkelijke getal geven als ze vermenigvuldigd worden. Zo is het getal $12$ bijvoorbeeld te ontbinden in de getallen $2$, $2$ en $3$, want $2 \cdot 2 \cdot 3 = 12$. De ontbinding $3$ en $4$ is fout, omdat $2$ kleiner is en je deze dus liever in je ontbinding wil hebben dan $4$. Het getal $1$ gebruiken we niet in een ontbinding, dus $2$ is het kleinste getal.

  1. Schrijf een programma dat de gebruiker om een (positief) getal vraagt en de ontbinding van dit getal geeft. De uitvoer moet van de volgende vorm zijn, als de gebruiker bijvoorbeeld het getal 12 invoert:

    12 = 2 * 2 * 3

Als je in Python twee prints wilt doen op dezelfde regel (en dus niet de tweede print op een nieuwe regel zoals normaal gesproken gebeurt), kun je de constructie print(x, end='') gebruiken, waarbij je voor x je variabelen/strings die je wilt printen invoert. Als je een extra nieuwe regel wilt printen, moet je de string \n printen. Let op: uit een gewone deling a/b komt een floating-point getal. Om het algoritme goed te laten werken heb je misschien een integer-deling nodig, a//b. Deze zorgt altijd voor exacte uitkomsten als het gaat om integers.

Misschien weet je al dat de getallen die hieruit komen priemgetallen zijn, oftewel getallen die alleen deelbaar zijn door $1$ en zichzelf. Dit wordt dan ook de priemfactorontbinding genoemd. Hint: je hoeft voor deze opdracht niet expliciet een lijst van priemgetallen te berekenen.

In de cryptografie is de priemfactorontbinding van grote getallen een belangrijk probleem. Dit is niet erg efficient uit te rekenen.

  1. Met time.time() kun je de huidige tijd opvragen (in seconden, sinds 1 januari 1970). Let erop dat je time importeert met import. Pas met behulp van deze functie je programma aan zodat aan het eind wordt geprint hoe lang de berekening geduurd heeft. Probeer daarna het getal $24297173736142264967522740376$ te ontbinden en meet hoe lang dat dit duurt. De computer heeft wat tijd nodig om dit getal te ontbinden!

In de cryptografie worden vaak getallen van meer dan 600 cijfers gebruikt. Om dit te ontbinden zou een computer honderden jaren bezig zijn.