Rozkładanie liczby na czynniki pierwsze
Rozkład liczby na czynniki pierwsze polega na zapisaniu danej liczby w postaci iloczynu liczb pierwszych. Jak dobrze wiemy liczby naturalne składają się z liczb pierwszych, które dzielą się przez jeden i samą siebie, oraz liczb złożonych, które mają co najmniej dwa dzielniki większe od jeden.
Przy małych liczbach można w pamięci znaleźć dzielniki, np:
$2: \text{liczba pierwsza} \\ 3: \text{liczba pierwsza} \\ 4: \text{liczba złożona, bo } 2\cdot 2=4 \\ 5: \text{liczba pierwsza} \\ 6: \text{liczba złożona, bo } 2\cdot 3=6 \\ 7: \text{liczba pierwsza} \\ 8: \text{liczba złożona, bo } 2\cdot 2\cdot2=8 \\ 9: \text{liczba złożona, bo } 3\cdot 3=9 \\ 10: \text{liczba złożona, bo } 2\cdot 5=10 \\ 11: \text{liczba pierwsza} \\ 12: \text{liczba złożona, bo } 2\cdot 2\cdot 3=12 \\ 13: \text{liczba pierwsza} \\ 14: \text{liczba złożona, bo } 2\cdot 7=14 \\ 15: \text{liczba złożona, bo } 3\cdot 5=15 \\ 16: \text{liczba złożona, bo } 2\cdot 2\cdot 2\cdot 2=16 \\ 17: \text{liczba pierwsza} \\ 18: \text{liczba złożona, bo } 2\cdot 3\cdot 3=18 \\ 19: \text{liczba pierwsza} \\ 20: \text{liczba złożona, bo } 2\cdot 2\cdot 5=20 \\$
Przy większych liczbach, aby je rozłożyć stosuje się pisemny algorytm rozkładania liczb na czynniki pierwsze. Dla przykładu rozłóżmy liczbę 124 na czynniki pierwsze.
$\begin{array}{c|lcr} 124 & 2 \\ 62 & 2 \\ 31 & 31 \\ 1 & \end{array}$
Rozkład liczby $124$ na czynniki pierwsze jest następujący: $124=2\cdot 2\cdot 31$.
Algorytm rozkładania liczby na czynniki pierwsze jest następujący: W lewej kolumnie zapisujemy liczbę, natomiast w prawej jej najmniejszy dzielnik, który dzieli ją bez reszty. Liczbę z lewej dzielimy przez liczbę z prawej, wynik zapisujemy w kolejnym rzędzie po lewej strony. Tą operację przeprowadzamy tyle razy, aż po lewej stronie uzyskamy liczbę jeden.