Przeczytaj
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.
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.
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.
Ponownie sprawdzamy, czy liczba po lewej stronie jest podzielna przez 2.
Tak. Powtarzamy więc czynność.
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.
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.
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.
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 whilewhile
(w pseudokodzie dopóki
).
Moglibyśmy użyć warunku liczbaDoSprawdzenia !=!= 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
.
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
.
Ostatnim krokiem jest przejście do kolejnej liczby, jeżeli liczba pierwsza
nie jest dzielnikiem liczbaDoSprawdzenia
.
Słownik
operator, który zwraca wartość true
, jeżeli dwa elementy nie są sobie równe oraz wartość false,
jeżeli są sobie równe
pętla, która wykonuje instrukcje w niej zawarte tak długo, jak zadane jej wyrażenie logiczne jest prawdziwe