Każda liczba naturalna n może zostać jednoznacznie zapisana jako iloczyn liczb pierwszych. Jednoznacznie oznacza, że istnieje tylko jeden zbiór liczb pierwszych, których iloczyn daje w wyniku podaną liczbę. Przy czym możemy tutaj wyróżnić dwa przypadki:
- liczby złożone - posiadają więcej niż jeden czynnik pierwszy
- liczby pierwsze - posiadają tylko jeden czynnik pierwszy (samą siebie)
Rozkład na czynniki pierwsze polega na znalezieniu dla danej liczby naturalnej n, n > 1, wszystkich liczb pierwszych, których iloczyn daje n.
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:
Przeanalizujmy 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
#include <iostream>
#include <cmath>
using namespace std;
void czynnikiPierwsze(unsigned n)
{
unsigned p, i;
//deklarujemy zmienna p i przypisujemy
//do niej pierwiastek z liczby n
p = sqrt(n);
for (i = 2; i <= p; i++) {
while (n % i == 0) {
cout << i << " ";
n /= i;
}
if (n == 1) {
cout << endl;
return;
}
}
cout << n << endl;
}
int main()
{
unsigned n;
cout << "Program rozklada liczbe naturalna n na czynniki pierwsze." << endl;
cout << "Podaj liczbe naturalna n wieksza od 1" << endl;
cin >> n;
cout << "Czynniki pierwsze liczby " << n << " to:" << endl;
czynnikiPierwsze(n);
cin.get();
return 0;
}