Autor artykułu: mgr Jerzy Wałaszek, wersja1.0
©2010 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
|
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