Pri riešení programátorských úloh portálu Codility, som narazil na zadanie nájsť počet deliteľov ľubovoľného čísla. Úroveň úlohy bola „painless“ – bez bolesti. V skutočnosti to však celkom zabolelo.
Riešenie ma napadlo rýchlo, tušil som však, že nebude príliš efektívne. Tento pocit sa potvrdil pri čísle 2,147,483,647 kedy moja logika zlyhala a bola ukončená pre príliš dlhé výpočty.
Ako to teda riešiť?
Každé číslo, nazvime ho n
, ktoré ma deliteľa a
, má zároveň i deliteľa n/a = b
. A teda a * b = n
.
Príklad: Číslo 24 má deliteľa 6 a preto má určite i druhého deliteľa, ktorého vypočítame ako 24 / 6 = 4.
No a tu prichádza na scénu krása matematiky.
Vždy je aspoň jeden z dvoch deliteľov čísla n menší ako odmocnina čísla n.
A teda odmocnina z 24 je 4,89. Vidíme, že číslo 4 je naozaj menšie ako 4,89. A takto to platí vždy. 1 a 24, 2 a 12, 3 a 8 atď. Vždy je aspoň jedno číslo menšie ako odmocnina z 24.
Potom je tu ešte prípad, kedy sa deliteľ priamo rovná odmocnine daného čísla: 9 = 3 * 3. Deliteľ 3 sa rovná odmocnine z 9.
A teda poďme na riešenie problému.
Chceme zistiť počet deliteľov napr. čísla 24. Postupujeme takto:
- 1 je menšie ako odmocnina z 24 a číslo 1 je deliteľ 24. 1*24 = 24. Máme teda prvé dva delitele (1, 24).
- 2 je menšie ako odmocnina z 24 a číslo 2 je deliteľ 24. 2*12 = 24. Máme teda druhé dva delitele (2, 12) .
- 3 je menšie ako odmocnina z 24 a číslo 3 je deliteľ 24. 3*8 = 24. Máme teda tretie dva delitele (3, 8) .
- 4 je menšie ako odmocnina z 24 a číslo 4 je deliteľ 24. 4*6 = 24. Máme teda štvrté dva delitele (4, 6) .
- 5 už však nie je menšie ako odmocnina z 24 a tu končíme.
Spolu máme teda 8 deliteľov.
Pri čísle 9 postupujeme podobne:
- 1 je menšie ako odmocnina z 9 a číslo 1 je deliteľ 9. 1*9 = 9. Máme teda prvé dva delitele (1, 9) .
- 2 je menšie ako odmocnina z 9 ale číslo 2 nie je deliteľ 9.
- 3 nie je menšie ako odmocnina z 9 ale číslo 3 je rovné odmocnine z 9 a preto máme ďalšieho deliteľa (3) .
Spolu máme 3 deliteľov.
Existujú aj iné spôsoby ako vypočítať počet deliteľov čísla. Tento je však veľmi jednoduché prepísať do kódu a dokáže vyriešiť úlohu efektívne, v čase O(sqrt(N)).
function solution($N) {
$result = 0;
$i=1;
while ($i * $i < $N ) {
if ($N % $i == 0) $result += 2;
$i++;
}
if ($i * $i == $N) $result++;
return $result;
}