Rozkład liczby na czynniki pierwsze
Czynnik pierwszy danej liczby naturalnej złożonej, to dowolna liczba pierwsza, która dzieli tę liczbę. Jedna z podstawowych obserwacji dotyczących liczb naturalnych mówi, że każdą liczbę złożoną można przedstawić za pomocą iloczynu liczb pierwszych, czyli rozłożyć na czynniki pierwsze. To wiedział już Euklides w IV w. p. n. e., który w słynnym dziele Elementy w księdze IX stwierdza, że każdą liczbę można jednoznacznie przedstawić jako iloczyn liczb pierwszych.
Każda liczba naturalna (n > 1) jest albo liczbą pierwszą albo iloczynem liczb pierwszych.
Każdą liczbę zatem można jednoznacznie zapisać za pomocą iloczynu liczb pierwszych, a kolejność zapisu tych liczb nie ma znaczenia. Zasada Euklidesa mówi, że liczba pierwsza dzieli iloczyn liczb tylko wtedy, gdy dzieli przynajmniej jedną z nich. Wynika zniej, że liczba nie może mieć dwóch różnych rozkładów na iloczyn liczb pierwszych.
Elementarnym sposobem rozkładu liczb na czynniki pierwsze jest kolejne dzielenie. Szukamy najmniejszej liczby pierwszej dzielącej daną liczbę i dzielimy. Powstały iloraz jest nową liczbą, dla której szukamy następną liczbę pierwszą ją dzielącą i powtarzamy tą czynność aż do uzyskania w ilorazie liczby 1. Otrzymujemy wówczas wszystkie dzielniki pierwsze szukanej liczby.
Dla dużych liczb metoda ta może nastręczać duże trudności z powodu długości potrzebnych rachunków, można więc wykorzystać maszynę do obliczeń, w tym celu należy napisać program, który w ułamku sekundy wymieni nam czynniki pierwsze danej liczby. Algorytm rozkładu liczb na czynniki pierwsze
