2862. Количество делителей

Найти количество делителей числа n.

Вход. Одно натуральное число n (n < 10000).

Выход. Количество делителей числа n.

Пример входа	Пример выхода
12	6

РЕШЕНИЕ

теория чисел – количество делителей

Анализ алгоритма

Если n = , то количество его делителей равно

d(n) = (a₁ + 1) * (a₂ + 1) * … * (a_k + 1)

Реализация алгоритма

Функция CountDivisors вычисляет количество делителей числа n.

int CountDivisors(int n)

{

int c, i, res = 1;

for(i = 2; i <= (int)sqrt(1.0*n); i++)

{

if (n % i == 0)

{

Если i – простой делитель числа n, то подсчитываем сколько раз он входит в n в переменной c.

c = 0;

while(n % i == 0)

{

n /= i; c++;

}

res *= (c + 1);

}

}

Если n > 1, то n содержит простой делитель.

if (n > 1) res *= 2;

return res;

}

Основная часть программы. Читаем входное значение n и выводим количество его делителей.

scanf("%d",&n);

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

Java реализация

import java.util.*;

public class Main

{

public static int CountDivisors(int n)

{

int c, res = 1;

for(int 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;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int res = CountDivisors(n);

System.out.println(res);

}

}

Python реализация

def CountDivisors(n):

res = 1

for i in range(2, 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())

res = CountDivisors(n)

print(res)