Потенцијални чиниоци \(f\) броја \(n\) се испитују редом, у петљи, кренувши од броја 2. У сваком кораку испитује се дa ли је број \(n\) дељив бројем \(f\) и док год јесте дељив, у унутрашњој петљи, он се дели бројем \(f\) пријављујући при том чинилац \(f\) (пошто се у склопу услова унутрашње петље врши провера дељивости \(n\) са \(f\), није потребна посебна провера дељивости наредбом гранања пре те петље). Након тога прелази се на следећи потенцијални чинилац (за један већи од претходног). Иако се може помислити да је за сваки потенцијални чинилац потребно проверити да ли је он прост број (јер нас занимају само прости чиниоци), то није потребно радити. Наиме, у поступку претраге који смо навели, ако текући кандидат \(f\) није прост, он не може да дели број \(n\), јер смо све његове просте чиниоце већ дељењем уклонили из броја \(n\). На пример, када \(f\) достигне вредност \(6\), број \(n\) не може бити дељив њиме јер је претходно исцрпно издељен бројем 2 (а касније и бројем 3). Заиста, ако претпоставимо супротно да \(f\) дели \(n\) и да је \(f\) сложен број, тада би \(f\) имаo неки прости чинилац мањи од њега и то би уједно био прост чинилац броја \(n\). Међутим, то није могуће јер смо пре увећања броја \(f\) на његову текућу вредност утврдили да текући број \(n\) не може бити дељив ни једним бројем мањем од \(f\) (иначе бисмо га делили са \(f\), а не увећавали \(f\)). Дакле сложени чиниоци се елиминишу тако што се утврди да текући број \(n\) није дељив њима, што је много ефикасније него примењивати на њих тест прималности.
У најједноставнијој имплементацији, описани поступак траје све док се број \(n\) дељењем својим чиниоцима не сведе на број 1.
Сложеност. Иако коректан, алгоритам који се завршава свођењем броја на 1 је прилично неефикасан и за бројеве који имају велике просте чиниоце ради веома споро (покушајте извршавање програма нпр. за број 1000000007). Проблем настаје јер се делиоци последњег простог чиниоца испитују све док се не дође до самог тог броја. С обзиром на ограничење бројевног типа, број чинилаца можемо сматрати практично константним (не може их бити више од 32), па је сложеност \(O(f_k)\), где је \(f_k\) највећи прост фактор полазног броја, што је \(O(n)\) када је \(n\) прост број.
На срећу, алгоритам је једноставно поправити, тако што се растављање заустави чим се утврди да је текућа вредност променљиве \(n\) прост број (а видећемо да за то није потребно чекати да вредност \(f\) достигне \(n\)).
Пример. Прикажимо рад алгоритма на једном примеру.
n f cinioc 3300 2 2 1650 2 2 825 2 - 825 3 3 275 3 - 275 4 - 275 5 5 55 5 5 11 5 - 11 6 - 11 7 - 11 8 - 11 9 - 11 10 - 11 11 11 1 11 -
Имплементација се може направити на следећи начин.
#include <iostream>
using namespace std;
int main() {
// ucitavamo broj koji treba rastaviti na proste cinioce
int n;
cin >> n;
int f = 2; // prvi potencijalni prost cinilac je 2
// dok se broj deljenjem sa svojim prostim ciniocima ne svede na 1
while (n > 1) {
while (n % f == 0) { // dok je n deljivo sa f
cout << f << " "; // prijavljujemo pronađeni prost cinilac
n /= f; // delimo broj njime
}
f = f + 1; // prelazimo na sledeceg kandidata
}
cout << endl;
return 0;
}Доказ коректности. Докажимо коректност претходног алгоритма и формално, коришћењем технике инваријанти петље. Централна инваријанта петље је то да текућа вредност променљиве \(n\) није дељива ни једним бројем из интервала \([2, f)\), као и да је почетни број \(n_0\) производ до сада исписаних простих бројева и текуће вредности променљиве \(n\).
Пре уласка у петљу је \(f=2\), па је интервал \([2, f)\) празан и први део инваријанте тривијално важи. Важи и да је \(n=n_0\) и да ниједан број није исписан, па и други део инваријанте важи.
Претпоставимо да инваријанта важи на уласку у петљу.
Ако је \(n\) дељив бројем \(f\), исписује се број \(f\). Он је очигледно чинилац броја \(n\). Претпоставимо да је сложен и да се може раставити као \(f = f_1 \cdot f_2\), за \(f_1 > 1\) и \(f_2 > 1\). Тада би број \(n\) био дељив са \(f_1\) и са \(f_2\) који припадају интервалу \([2, f)\), што је супротно инваријанти, па закључујемо да \(f\) мора бити прост. Дељењем броја \(n\) са \(f\) добија се нови број \(n'\), који такође није дељив ни са једним бројем из \([2, f)\), па први део инваријанте остаје очуван. Почетна вредност \(n_0\) остаје једнака производу исписаних бројева и текуће вредности \(n\) (јер је то важило на основу инваријанте, исписано је \(f\), а \(n\) је подељено са \(f\)), па и други део инваријанте остаје очуван.
Ако \(n\) није дељив бројем \(f\), тада се \(f\) увећава за 1 (нека је \(f' = f+1\)). Да би први део инваријанте био одржан, треба да важи да \(n\) није дељив ни са једним бројем из интервала \([2, f') = [2, f]\), но то важи, јер на основу инваријанте знамо да \(n\) није дељив ни са једним бројем из интервала \([2, f)\), а на основу експлицитне провере услова знамо да \(n\) није дељиво ни са \(f\). Ниједан број није исписан, нити је број \(n\) промењен, па други део инваријанте тривијално наставља да важи.
На основу инваријанте знамо да је \(n_0\) једнак производу свих исписаних простих чинилаца и тренутне вредности броја \(n\). Пошто је када се алгоритам заврши она једнака \(1\), исписана је проста факторизација броја \(n\).