Algoritmos y Estructuras de Datos

Cantidad de divisores con factorización en primos

Un enfoque ingenuo para encontrar la cantidad de divisores de un entero positivo n consiste en recorrer todos los números desde 1 hasta n (inclusive) y contar cuántos de ellos dividen a n.
Sin embargo, este método es muy lento. Podemos calcular el número de divisores de n a través de sus factores primos (encontrar los factores primos toma únicamente tiempo ).
Imagina que un número se representa como el producto de sus factores primos:
Podemos calcular la cantidad de divisores de n tomando todos sus exponentes, sumándoles 1 y multiplicando esos resultados entre sí:
Podemos implementarlo de manera muy similar a como encontramos todos los factores primos de n:
n = ...
p, divisors = 1, 1          # factor primo y el número de divisores

while p * p <= n:           # mientras p <= sqrt(n)
    p += 1                  # Suma 1 al factor primo en cada iteración
    if n % p != 0:          # No hagas nada si n no es divisible entre p
        continue
    
    exp = 0                 # contador para el exponente
    while n % p == 0:       # divide tantas veces como sea posible
        n //= p
        exp += 1
    divisors *= exp + 1     # actualiza el producto

if n > 1:                   # si p > sqrt(n) => n es en sí mismo un factor primo
    divisors *= 2           # agrega n como divisor con exponente 1
print(divisors)

Desafío: Encontrar el número de divisores de n

Dado un entero n, se te pide determinar cuántos divisores tiene n.

Entrada

La primera línea de la entrada contiene un único entero n (2 ≤ n ≤ ).

Salida

El programa debe imprimir la cantidad de divisores de n.

Ejemplos

Entrada
Salida
8
4
17
2
2048
12
48
10
Bonus: ¿Por qué al tomar todos los exponentes, sumarlos con 1 y multiplicarlos entre sí obtenemos el total de divisores de n?
La idea detrás de la fórmula para encontrar el número de divisores de n surge de considerar la cantidad de combinaciones posibles de sus factores primos. El exponente de cada factor indica cuántas veces puede usarse en la combinación que forma un divisor de n. Al sumar 1 a cada exponente, se incluyen las combinaciones que utilizan 0 de ese factor (esto permite contar tanto al propio n como al 1 como divisores de n). El resultado final de multiplicar cada (exponente + 1) abarca todas las combinaciones posibles de los factores primos y, por lo tanto, ofrece el total de divisores de n.
 

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue