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

Count factors

0

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:

Spolu máme teda 8 deliteľov.

Pri čísle 9 postupujeme podobne:

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

6 júla, 2019

Zanechať komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *