Rozkład liczby na czynniki pierwsze

Czynnik pierwszy liczby naturalnej, 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 z niej, ż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 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 czynniki pierwsze szukanej liczby.

Przykład
$780 \div \boxed{2} = 390$
$390 \div \boxed{2} = 195$
$195 \div \boxed{3} = 65$
$65 \div \boxed{5} = 13$
$13 \div \boxed{13} = 1$
$780 = 2 \cdot 2 \cdot 3 \cdot 5 \cdot 13$

Dla dużych liczb metoda ta może nastręczać duże trudności z powodu długości potrzebnych rachunków lub wykorzystania dużych liczb pierwszych, można więc wykorzystać maszynę do obliczeń, która w ułamku sekundy wymieni nam czynniki pierwsze danej liczby. Algorytm rozkładu liczb na czynniki pierwsze