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 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 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ń, która w ułamku sekundy wymieni nam czynniki pierwsze danej liczby. Algorytm rozkładu liczb na czynniki pierwsze


Rozłóż liczbę naturalną większą od 1 na czynniki pierwsze.

matematyka » arytmetyka » liczby pierwsze » rozkład liczb na czynniki pierwsze




gość logowanie

© 2014 Mariusz Śliwiński      mapa | o serwisie | kontakt | rss online: 85 drukuj