Na czym polega rozkład na czynniki pierwsze?

Każda liczba całkowita większa od 1 jest liczbą pierwszą albo liczbą złożoną.

Liczby pierwsze mają tylko dwa dzielniki: 1 oraz samą siebie. Z kolei liczba złożona jest taką liczbą, którą można przedstawić jako iloczyn innych liczb pierwszych. Dla przykładu: zapiszemy kilka liczb naturalnych jako iloczyn liczb pierwszych. I tak:

2 – jest liczbą pierwszą,

3 – jest liczbą pierwszą,

4 – liczbą złożoną, którą możemy przedstawić jako 2 * 2,

5 – jest liczbą pierwszą,

6 – liczbą złożoną, którą możemy przedstawić jako 2 * 3,

7 – jest liczbą pierwszą,

8 – liczbą złożoną, którą możemy przedstawić jako 2 * 2 * 2,

...

Dla małych liczb taki rozkład jest stosunkowo prosty. Natomiast dla większych znalezienie czynników pierwszych, bez znajomości konkretnej metody, nie jest już takie łatwe.

Metoda rozkładu liczby na czynniki pierwsze

Omówimy metodę, która znacznie ułatwia znajdowanie czynników pierwszych każdej liczby. Rozpoczynamy od zapisania liczby, którą chcemy rozłożyć na czynniki pierwsze w sąsiedztwie długiej, pionowej linii.

R17qnb3eNr5cV

Ilustracja przedstawia pionowa prostą i liczbę 136 po lewej stronie.

Następnie bierzemy najmniejszą liczbę pierwszą, czyli 2, i sprawdzamy, czy 136 jest podzielne przez 2.

Liczba 136 jest podzielna przez 2, więc po prawej stronie linii zapisujemy 2, a po lewej, poniżej naszej liczby, zapisujemy wynik dzielenia.

R1CxvoRc44ZVU

Ilustracja przedstawia Metodę rozkładu liczby na czynniki pierwsze.
po lewej stronie znajduje się liczba 136, dzielnik 2 po prawej, po lewej 68.

Powstałą liczbę dzielimy przez 2 tak długo jak długo 2 jest jej podzielnikiem Czy 68 jest podzielne przez 2?

Tak. Zapisujemy więc liczbę 2 po prawej stronie, a wynik z dzielenia po lewej stronie.

R1OHadrNXjqA5

Ilustracja przedstawia Metodę rozkładu liczby na czynniki pierwsze.
po lewej stronie znajduje się liczba 136, dzielnik 2 po prawej, po lewej 68, po prawej 2, po lewej 34.

Ponownie sprawdzamy, czy liczba po lewej stronie jest podzielna przez 2.

Tak. Powtarzamy więc czynność.

RB0aJKIZy0QAj

Ilustracja przedstawia Metodę rozkładu liczby na czynniki pierwsze.
po lewej stronie znajduje się liczba 136, dzielnik 2 po prawej, po lewej 68, po prawej 2, po lewej 34, po prawej 2, po lewej 17.

Czy liczba 17 jest podzielna przez 2?

Nie jest. Przestajemy więc dzielić przez 2 i przechodzimy do kolejnej liczby pierwszej, jaką jest 3. Czy 17 dzieli się przez 3? Sprawdźmy.

Niestety nie. Kontynuujemy więc przechodzenie do kolejnych liczb pierwszych, aż znajdziemy taką, która będzie dzielnikiem naszej liczby. Ponieważ liczba 17 jest liczbą pierwszą, jedynym takim dzielnikiem będzie liczba 17.

Zapisujemy więc liczbę 17 po prawej stronie linii oraz liczbę 1 po lewej stronie.

RH6YLOLxZVErA

Ilustracja przedstawia Metodę rozkładu liczby na czynniki pierwsze.
po lewej stronie znajduje się liczba 136, dzielnik 2 po prawej, po lewej 68, po prawej 2, po lewej 34, po prawej 2, po lewej 17 po prawej 17, po lewej 1.

Nasza liczba po lewej stronie osiągnęła wartość 1. W tym momencie nasz algorytm kończy swoje działanie. Liczby, które znajdują się po prawej stronie kreski, są czynnikami pierwszymi liczby 136. Chcąc upewnić się, że nie popełniliśmy błędu, możemy obliczyć ich iloczyn i sprawdzić, czy wynik będzie równy 136.

Wszystko się zgadza, algorytm dał poprawny wynik. Chcąc napisać program komputerowy, który będzie rozkładał liczby na czynniki pierwsze, zapiszemy algorytm w postaci pseudokodu. 

Algorytm rozkładu liczby na czynniki pierwsze

Spróbujmy napisać w pseudokodzie algorytm rozkładający liczbę na czynniki pierwsze, wzorując się na algorytmie opisanym powyżej. Pierwszym krokiem będzie inicjacja zmiennej, która będzie przechowywać liczbę do sprawdzenia.

liczbaDoSprawdzenia = liczba naturalna podana przez użytkownika

Będziemy również potrzebowali zmiennej, która będzie przechowywać liczbę pierwszą, znajdującą się w danym momencie po prawej stronie linii. Nazwiemy ją pierwsza i zainicjalizujemy liczbą 2, gdyż jest to najmniejsza liczba pierwsza.

liczbaDoSprawdzenia = liczba naturalna podana przez użytkownika
pierwsza = 2

Następnie będziemy dzielić liczbę po lewej stronie linii, aż do momentu, w którym jej wartość wyniesie 1. Do tego celu użyjemy pętli whilepętla whilewhile (w pseudokodzie dopóki).

liczbaDoSprawdzenia = liczba naturalna podana przez użytkownika
pierwsza = 2

dopóki liczbaDoSprawdzenia > 1 wykonuj:

Moglibyśmy użyć warunku liczbaDoSprawdzenia !=operator !=!= 1, ale starajmy się zawsze używać nierówności, jeżeli jest tylko taka możliwość. Jeżeli z jakiegoś powodu liczbaDoSprawdzenia ominęłaby wartość 1, pętla nigdy nie zakończyłaby działania  (w kolejnych e‑materiałach poznasz takie przypadki). W przypadku nierówności, nawet jeżeli nasza zmienna ominie wartość 1, pętla zakończy działanie.

Kolejnym krokiem jest dzielenie liczby po lewej stronie linii przez liczbę pierwszą, zapisaną w zmiennej pierwsza, dopóki jest ona jej dzielnikiem. Aby to osiągnąć, użyjemy kolejnej pętli dopóki.

liczbaDoSprawdzenia = liczba naturalna podana przez użytkownika
pierwsza = 2

dopóki liczbaDoSprawdzenia > 1 wykonuj:
    dopóki liczbaDoSprawdzenia mod pierwsza == 0 wykonuj:

Jeżeli liczba pierwsza jest dzielnikiem liczby do sprawdzenia, musimy wypisać do konsoli liczbę pierwsza, ponieważ jest ona czynnikiem pierwszym naszej liczby, a następnie podzielić liczbaDoSprawdzenia przez pierwsza.

liczbaDoSprawdzenia = liczba naturalna podana przez użytkownika
pierwsza = 2

dopóki liczbaDoSprawdzenia > 1 wykonuj:
    dopóki liczbaDoSprawdzenia mod pierwsza == 0 wykonuj:
        wypisz pierwsza
        liczbaDoSprawdzenia = liczbaDoSprawdzenia / pierwsza

Ostatnim krokiem jest przejście do kolejnej liczby, jeżeli liczba pierwsza nie jest dzielnikiem liczbaDoSprawdzenia.

liczbaDoSprawdzenia = liczba naturalna podana przez użytkownika
pierwsza = 2

dopóki liczbaDoSprawdzenia > 1 wykonuj:
    dopóki liczbaDoSprawdzenia mod pierwsza == 0 wykonuj:
        wypisz pierwsza
        liczbaDoSprawdzenia = liczbaDoSprawdzenia / pierwsza
  
    pierwsza = kolejna liczba pierwsza

Słownik