Rozważmy Twój przykład liczby 20. Tak jak podałeś (poprawnie), liczby pierwsze do pierwiastka z 20 (czyli ok. 4,5) to: 2 oraz 3. Algorytm faktoryzacji wygląda następująco:
faktoryzacja(n):
w pętli(i = 2, i <= sqrt(n),):
jeżeli (n mod i == 0):
n /= i
wypisz(i)
else
i ++
wypisz(n)
Dla liczby 20 program zadziała następująco:
poczatek funkcji
liczba = 20, i = 2:
(20 mod 2 == 0) ? TAK, wiec:
20 = 20 / 2 = 10
wypisz(2)
liczba = 10, i = 2:
(10 mod 2 == 0) ? TAK, wiec:
10 = 10 / 2 = 5
wypisz(2)
liczba = 5, i = 2:
(5 mod 2 == 0) ? NIE, wiec:
i = i + 1 = 2 + 1 = 3
liczba = 5, i = 3:
(5 mod 3 == 0) ? NIE, więc:
i = i + 1 = 3 + 1 = 4
i jest większe od sqrt(n), wiec petla konczy dzialanie
na koniec wypisz(n, czyli 5)
koniec funkcji, twoj program wypisal: 2 2 5,
czyli poprawny rozklad liczby 20 na czynniki pierwsze,
inaczej dokonał faktoryzacji liczby 20
Tutaj implementacja w języku C++:
#include <iostream>
using namespace std;
void fact(int n);
int main() {
int n;
cin >> n;
fact(n);
}
void fact(int n) {
for (int i = 2; i * i <= n;) {
if (n % i == 0) {
n /= i;
cout << i << ' ';
}
else
i ++;
}
cout << n;
}