Krásy matematiky – Počet deliteľov čísla

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;
}