Bölənlərin sayı#4742

Bölənlərin sayı (Həll təhlili)

$d (n)$ ədədinin bölənlərinin sayını ifadə etsin. Aydındır ki, $d (1) = 1$ d(1) = 1.

Tutaq ki, $p$ sadə ədəddir. Onda $p$ iki bölənə malikdir: $1$ və $p$ . Beləliklə, $d (p) = 2$ d(p) = 2.

Tutaq ki, $n = p^{k}$ n = p^k sadə ədədin qüvvətidir. Onda $n$ $(k + 1)$ (k + 1) bölənə malikdir: $1, p, p_{2}, p_{3}, ..., p^{k}$ 1, p, p_2, p_3, ..., p^k. Deməli, $d (p^{k}) = k + 1$ d(p^k) = k + 1.

Tutaq ki, $n = p^{k} q^{l}$ n = p^k q^l. İki çoxluq düşünək: $P = 1, p, p_{2}, p_{3}, ..., p_{k}$ P ={1, p, p_2, p_3, ..., p_k} və $Q = 1, q, q_{2}, q_{3}, ..., q_{l}$ Q = {1, q, q_2, q_3, ..., q_l}

Hər hansı $p^{k} q^{l}$ p^k q^l ədədinin bölənini $d = x \cdot y$ d = x \cdot y şəklində təsvir etmək olar, burada $x \in P, y \in Q$ x \in P, y \in Q. $P$ –dəki $x$ bölənini $k + 1$ k + 1 yolla, $Q$ –dəki $y$ bölənini isə $l + 1$ l + 1 yolla seçmək olar. Beləliklə, $d = x \cdot y$ d = x \cdot y bölənini $(k + 1) \cdot (l + 1)$ (k + 1) \cdot (l + 1) yolla yığmaq olar.

$n$ ərazıasında sadə bölüklərə ayıraq: $n = p_{1}^{a_{1}} p_{2}^{a_{2}} ... p_{k}^{a_{k}}$ n = p_1^{a_1}p_2^{a_2}...p_k^{a_k}. $n$ ədədinin bölənlərinin sayı

d (n) = (a_{1} + 1) \cdot (a_{2} + 1) \cdot ... \cdot (a_{k} + 1)

d(n) = (a_1 + 1) \cdot (a_2 + 1) \cdot ... \cdot (a_k + 1)

Nümunə

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

$n = 18$ n = 18 ədədini sadə bölüklərə ayıraq:

18 = 2 \cdot 3^{2}

18 = 2 \cdot 3^2

Beləliklə

d (18) = (1 + 1) \cdot (2 + 1) = 2 \cdot 3 = 6

d(18) = (1 + 1) \cdot (2 + 1) = 2 \cdot 3 = 6

İki böləni ( $1$ və $18$ ) çıxırıq, nəticə: $4$ bölən.

Alqoritmin icrası

CountDivisors funksiyası $n$ ədədini sadə bölüklərə ayırır və onun bölənlərinin sayını $d (n)$ hesablamaq üçün istifadə edir.

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

C++

Proqramın əsas hissəsi. Giriş qiyməti $n$ oxunur.

scanf("%d",&n);

Nəticəni hesablamaq və çap etmək. Ümumi bölənlərin sayından $d (n)$ iki böləni çıxırıq: $1$ və öz ədədi $n$ .

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

Python icrası

import math

CountDivisors funksiyası $n$ ədədini sadə bölüklərə ayırır və onun bölənlərinin sayını $d (n)$ hesablamaq üçün istifadə edir.

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;

Python

Proqramın əsas hissəsi. Giriş qiyməti $n$ oxunur.

n = int(input())

Nəticəni hesablamaq və çap etmək. Ümumi bölənlərin sayından $d (n)$ iki böləni çıxırıq: $1$ və öz ədədi $n$ .

print(CountDivisors(n) - 2)