![]() |
![]() ![]()
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2010 mgr Jerzy Wałaszek |
Pomoce:
Zbiór liczb naturalnych większych od 1 dzieli się na dwa rodzaje liczb:
Liczby pierwsze, które nie są iloczynami żadnych mniejszych liczb z tego zbioru: 2, 3, 5, 7, 11, 13, 17, 19...
Liczby złożone, które są iloczynami liczb mniejszych: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18...
Rozkład na czynniki pierwsze (ang. prime factorization) polega na znalezieniu dla danej liczby naturalnej n, n > 1, wszystkich liczb pierwszych, których iloczyn daje n. Zadanie to można rozwiązać na kilka różnych sposobów, jednakże nie istnieje żaden prosty wzór, który by pozwolił łatwo wyznaczać wszystkie czynniki pierwsze rozkładu - należy ich szukać. My podejdziemy do problemu w sposób następujący:
Daną liczbę n będziemy próbowali dzielić przez kolejne liczby i od 2 do pierwiastka z n. Jeśli dzielenie przez i jest możliwe (dostajemy resztę z dzielenia równą 0), to zapamiętamy czynnik i, podzielimy przez niego n i operację powtórzymy. Gdy dzielenie przestanie być już możliwe, sprawdzimy, czy n nie zredukowało się nam do 1. W takim przypadku znaleźliśmy już wszystkie czynniki dzielące n i algorytm przerwiemy. Jeśli n będzie wciąż większe od 1, to nie znaleźliśmy jeszcze wszystkich czynników. Dzielnik i zwiększamy o 1 i znów próbujemy dzielić. Gdy i przekroczy wartość pierwiastka z początkowego n, to ostatni czynnik jest większy od tego pierwiastka i znajduje się w bieżącej wartości n - wystarczy zatem zapamiętać ten ostatni czynnik i zakończyć algorytm.
Przykład:
Znajdziemy rozkład liczby n = 36:
Pierwiastek z 36 wynosi 6, zatem dzielniki będą kolejno przyjmowały wartości od 2 do 6:
36 : 2 = | 18 | - dzieli się, czynnik 2 |
18 : 2 = | 9 | - dzieli się, czynniki 2 2 |
9 : 2 = | - nie dzieli się, bierzemy kolejny dzielnik 3 | |
9 : 3 = | 3 | - dzieli się, czynniki 2 2 3 |
3 : 3 = | 1 | - dzieli się, czynniki 2 2 3 3 - koniec, gdyż n zredukowało się do 1 |
36 = 2 × 2 × 3 × 3
Znajdziemy rozkład liczby n = 66:
Pierwiastek z 66 wynosi 8,12..., dzielniki od 2 do 8.
66 : 2 = | 33 | - dzieli się, czynnik 2 |
33 : 2 = | - nie dzieli się, bierzemy kolejny dzielnik 3 | |
33 : 3 = | 11 | - dzieli się, czynniki 2 3 |
11 : 3 = | - nie dzieli się, bierzemy kolejny dzielnik 4 | |
11 : 4 = | - nie dzieli się, bierzemy kolejny dzielnik 5 | |
11 : 5 = | - nie dzieli się, bierzemy kolejny dzielnik 6 | |
11 : 6 = | - nie dzieli się, bierzemy kolejny dzielnik 7 | |
11 : 7 = | - nie dzieli się, bierzemy kolejny dzielnik 8 | |
11 : 8 = | - nie dzieli się, koniec, ponieważ wykorzystaliśmy wszystkie dzielniki, czynniki 2 3 11 |
66 = 2 × 3 × 11
Wejście:
n - liczba naturalna, której rozkładu
poszukujemy, n > 1.
Wyjście:
Czynniki pierwsze liczby n.
Dane pomocnicze:
g - wartość pierwiastka z n
i - dzielniki
Krok 1: | g ← √n | ; wyznaczamy górną granicę podzielników |
Krok 2: | i ← 2 | ; ustalamy pierwszy dzielnik |
Krok 3: | Jeśli i > g, to idź do kroku 11 | ; sprawdzamy, czy przetworzono wszystkie dzielniki |
Krok 4: | Jeśli n nie dzieli się przez i, to idź do kroku 8 | ; sprawdzamy, czy i jest czynnikiem n |
Krok 5: | Pisz i | ; jest, wyprowadzamy czynnik i |
Krok 6: | n ← n / i | ; usuwamy czynnik i z n |
Krok 7: | Idź do kroku 4 | ; powtarzamy sprawdzenie podzielności n przez i |
Krok 8: | Jeśli n = 1, to zakończ | ; sprawdzamy, czy znaleziono wszystkie czynniki pierwsze |
Krok 9: | i ← i + 1 | ; nie, bierzemy następny dzielnik |
Krok 10: | Idź do kroku 3 | ; i powtarzamy test |
Krok 11: | Pisz n | ; w n pozostał czynnik większy od pierwiastka z n |
Krok 12: | Zakończ |
// Rozkład na czynniki pierwsze // (C)2010 I LO w Tarnowie //------------------------ #include <iostream> #include <cmath> using namespace std; // Funkcja wypisuje wszystkie czynniki pierwsze liczby n //------------------------------------------------------ void czynniki(unsigned n) { unsigned g,i; g = sqrt(n); for(i = 2; i <= g; i++) { while(n % i == 0) { cout << i << " "; n /= i; } if(n == 1) { cout << endl; return; } } cout << n << endl; } int main() { unsigned n; cin >> n; czynniki(n); return 0; } |
Wykorzystaj powyższy program do znajdowania rozkładu na czynniki pierwsze kolejnych liczb naturalnych od 2 do zadanej wartości n.
![]() | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe