Number of divisors#4742

Number of divisors (Editorial)

Let $d (n)$ be the number of divisors of $n$ . Obviously, $d (1) = 1$ d(1) = 1.

Let $p$ be a prime integer. Then $p$ has two divisors: $1$ and $p$ . Therefore, $d (p) = 2$ d(p) = 2.

Let $n = p^{k}$ n = p^k be a power of a prime number. Then $n$ has $k + 1$ k + 1 divisors: $1, p, p_{2}, p_{3}, ..., p^{k}$ 1, p, p_2, p_3, ..., p^k. Hence, $d (p^{k}) = k + 1$ d(p^k) = k + 1.

Let $n = p^{k} q^{l}$ n = p^k q^l. Consider two sets: $P = 1, p, p_{2}, p_{3}, ..., p_{k}$ P ={1, p, p_2, p_3, ..., p_k} and $Q = 1, q, q_{2}, q_{3}, ..., q_{l}$ Q = {1, q, q_2, q_3, ..., q_l}

Any divisor $d$ of the number $p^{k} q^{l}$ p^k q^l can be represented in the form $x \cdot y$ x \cdot y, where $x \in P, y \in Q$ x \in P, y \in Q. A divisor $x$ from $P$ can be chosen in $k + 1$ k + 1 ways, and a divisor $y$ from $Q$ can be chosen in $l + 1$ l + 1 ways. Therefore, a divisor $d = x \cdot y$ d = x \cdot y can be formed in $(k + 1) \cdot (l + 1)$ (k + 1) \cdot (l + 1) ways.

Decompose the number $n$ into its prime factors: $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}. The number of divisors of $n$ is equal to

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)

Example

The number $n = 18$ n = 18 has $6$ divisors: $1, 2, 3, 6, 9, 18$ 1, 2, 3, 6, 9, 18.

Let's decompose the number $n = 18$ n = 18 into its prime factors:

18 = 2 \cdot 3^{2}

18 = 2 \cdot 3^2

Therefore

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

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

Subtracting two divisors ( $1$ and $18$ ), we get the answer: $4$ divisors.

Algorithm implementation

The function CountDivisors decomposes the number $n$ into its prime factors and calculates the number of its divisors $d (n)$ .

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++

The main part of the program. Read the value of $n$ .

scanf("%d",&n);

Calculate and print the answer. From the total number of divisors $d (n)$ subtract two divisors: $1$ and the number $n$ itself.

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

Python implementation

import math

The function CountDivisors decomposes the number $n$ into its prime factors and calculates the number of its divisors $d (n)$ .

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

The main part of the program. Read the value of $n$ .

n = int(input())

Calculate and print the answer. From the total number of divisors $d (n)$ subtract two divisors: $1$ and the number $n$ itself.

print(CountDivisors(n) - 2)