Rozkład liczby naturalnej na iloczyn liczb pierwszych metodą kolejnych dzielników – z animowaną wizualizacją.
Rozkład na czynniki pierwsze (inaczej faktoryzacja) to zapisanie liczby jako mnożenia samych liczb pierwszych. Na przykład 360 = 2 · 2 · 2 · 3 · 3 · 5. Każdą liczbę większą od 1 da się tak rozłożyć i tylko na jeden sposób – kolejność czynników może być inna, ale te same liczby zawsze wyjdą. To znane twierdzenie z matematyki, więc nie musisz się martwić, że dla jakiejś liczby rozkład „nie wyjdzie".
Jak to działa? Najprościej sprawdzać po kolei dzielniki. Bierzemy d = 2 i dopóki d dzieli n bez reszty, dopisujemy d do wyniku i dzielimy przez nie n. Gdy d już nie dzieli, zwiększamy je o 1 i próbujemy dalej. Ważny trik: zanim dojdziemy do jakiegoś większego dzielnika, wszystkie mniejsze są już „wyciągnięte" z liczby. Dzięki temu każdy dopisany dzielnik jest z automatu pierwszy – nie musimy tego osobno sprawdzać.
Dlaczego wystarczy sprawdzać do pierwiastka? Dzielniki chodzą parami: jeśli d dzieli n, to n/d też jest dzielnikiem. Jedna liczba z takiej pary jest zawsze ≤ √n. Gdy więc dojdziemy z d do pierwiastka i nic już nie dzieli, a n wciąż jest większe od 1, to znaczy, że to, co zostało, samo jest liczbą pierwszą – i to nasz ostatni czynnik.
Na maturze: rozkład to cegiełka wielu zadań – liczenie NWD i NWW, liczba i suma dzielników, sprawdzanie, czy liczba jest kwadratem albo sześcianem. Warto też wiedzieć, że rozkładanie naprawdę dużych liczb jest bardzo trudne i wolne – i właśnie na tym opiera się bezpieczeństwo szyfru RSA.
Prześledź krok po kroku metodę kolejnych dzielników (trial division): algorytm próbuje d = 2, 3, 4, … Gdy d dzieli n bez reszty, odrywa czynnik pierwszy i skraca n przez d; gdy nie – zwiększa d. Sprawdza tylko do √n, a jeśli coś zostanie większe od 1, to też jest czynnikiem pierwszym.
Naciśnij „Krok", aby sprawdzić pierwszy dzielnik, albo „Auto".
funkcja rozklad_pierwszy(n): czynniki ← pusta lista d ← 2 dopóki d * d ≤ n: dopóki n mod d = 0: dodaj d do czynniki // d jest pierwsze n ← n div d // zdejmij ten czynnik d ← d + 1 jeżeli n > 1: dodaj n do czynniki // to, co zostało, też jest pierwsze zwróć czynniki
def rozklad_na_czynniki(n):
"""Zwraca listę czynników pierwszych liczby n (rosnąco)."""
czynniki = []
d = 2
while d * d <= n:
while n % d == 0:
czynniki.append(d) # d jest pierwsze
n //= d # zdejmij ten czynnik
d += 1
# jeśli coś zostało, to ostatni czynnik pierwszy
if n > 1:
czynniki.append(n)
return czynniki
# Przykłady użycia
print(rozklad_na_czynniki(360)) # Wynik: [2, 2, 2, 3, 3, 5]
print(rozklad_na_czynniki(97)) # Wynik: [97]#include <vector>
#include <iostream>
using namespace std;
vector<int> rozklad_na_czynniki(int n) {
vector<int> czynniki;
for (int d = 2; (long long)d * d <= n; d++) {
while (n % d == 0) {
czynniki.push_back(d); // d jest pierwsze
n /= d; // zdejmij ten czynnik
}
}
if (n > 1) czynniki.push_back(n); // ostatni czynnik pierwszy
return czynniki;
}
int main() {
for (int x : rozklad_na_czynniki(360)) cout << x << " ";
// Wynik: 2 2 2 3 3 5
}To liczba pierwsza, przez którą dzieli się nasza liczba. Na przykład 12 to 2 · 2 · 3, więc jej czynniki pierwsze to dwie dwójki i trójka.
Bo dzielniki chodzą w parach: jeśli jeden jest większy od pierwiastka, to drugi z pary jest od niego mniejszy. Gdy więc do pierwiastka nic nie znaleźliśmy, to znaczy, że liczba, która została, jest już pierwsza.
Nie. Jeśli najpierw wyciągniesz wszystkie dwójki, potem wszystkie trójki i tak dalej, to złożony dzielnik (np. 4) nigdy nie podzieli liczby – jego mniejsze kawałki zostały zdjęte wcześniej.
Przy liczeniu NWD i NWW, przy sprawdzaniu, czy liczba jest kwadratem, oraz w wielu maturalnych zadaniach o liczbach. W praktyce trudność rozkładania dużych liczb chroni też szyfr RSA.
Uzupełnij rozkłady i kliknij Sprawdź.
Liczba 12 to `2 · 2 · . Liczba 18 to 2 · 3 · . Liczba 20 to 2 · 2 · `.
Liczba 7 jest pierwsza, więc jej rozkład to po prostu .
Uzupełnij tabelę (wpisz brakujący czynnik):
| Liczba | Rozkład |
|---|---|
| 8 | 2 · 2 · |
| 45 | 3 · 3 · |
| 50 | 2 · 5 · |
O(√n)O(log n)Czas O(√n). Dzielnik d rośnie najwyżej do pierwiastka z n (warunek d · d ≤ n), a same dzielenia tylko skracają n, więc nie psują tego rzędu. Najgorszy przypadek to liczba pierwsza – wtedy nic po drodze nie „urywa" liczby i trzeba przejść pełne √n prób.
Pamięć O(log n). Sam algorytm potrzebuje tylko kilku zmiennych, ale rośnie lista czynników. Najwięcej czynników ma potęga dwójki (n = 2·2·2·…), a tych dwójek jest około log₂ n – stąd taki rozmiar wyniku.
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: