Alqoritm Analizi

Bir $n$ ədədinin bölənlərinin sayını $d(n)$ ilə işarə edək. Açıqdır ki, $d(1)=1$.

$p$ ədədi əsas ədəd olsun. Onda $p$-nin iki böləni var: 1 və $p$. Beləliklə, $d(p)=2$.

$n=p^k$ ədədi bir əsas ədədin qüvvəti olsun. Onda $n$-in $k+1$ böləni var: 1, $p$, $p^2$, $p^3$, …, $p^k$. Beləliklə, $d(p^k)=k+1$.

$n=p^k{q}^l$ olsun. İki dəstəni nəzərdən keçirək:

$P=\{1,p,p^2,p^3,\dots ,p^k\}$ və $Q=\{1,q,q^2,q^3,\dots ,q^l\}$

$p^k{q}^l$ ədədinin hər hansı bir böləni $d$ $x\ast y$ kimi təsvir edilə bilər, burada $x\in P,y\in Q$. $P$ dəstəsindən $x$ böləni $k+1$ şəkildə, $Q$ dəstəsindən $y$ böləni $l+1$ şəkildə seçilə bilər. Beləliklə, $d=x\ast y$ böləni $(k+1)\ast (l+1)$ şəkildə formalaşdırıla bilər.

$n$ ədədini əsas amillərə ayıraq: $n=p_1^{a_1}{p}_2^{a_2}...p_k^{a_k}$. $n$ ədədinin bölənlərinin sayı

Nümunə

$n=18$ ədədinin 6 böləni var: 1, 2, 3, 6, 9, 18.

$n=18$ ədədini əsas amillərə ayıraq:

$18=2\ast 3^2$

Beləliklə

İki bölən (1 və 18) çıxardıldıqda cavabı alırıq: 4 bölən.

Alqoritm Tətbiqi

CountDivisors funksiyası $n$ ədədini əsas amillərə ayırır və onun bölənlərinin sayını $d(n)$ hesablayır.

int CountDivisors(int n)
{
    int c, i, res = 1;
    for(i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            c = 0;
            while(n % i == 0)
            {
                n /= i;
                c++;
            }
            res *= (c + 1);
        }
    }
    if (n > 1) res *= 2;
    return res;
}

Proqramın əsas hissəsi. Giriş dəyəri $n$-i oxuyuruq.

scanf("%d",&n);

Cavabı hesablayıb göstəririk. $d(n)$-in ümumi bölənlərinin sayından iki bölən çıxarırıq: 1 və öz $n$ ədədi.

printf("%d\n",CountDivisors(n)-2);

Python Tətbiqi

import math

def CountDivisors(n):
    res = 1
    for i in range(2, int(math.sqrt(n)) + 1):
        if (n % i == 0):
            c = 0
            while (n % i == 0):
                n //= i
                c += 1
            res *= (c + 1)
    if (n > 1): res *= 2
    return res

n = int(input())
print(CountDivisors(n) - 2)