Algoritmos e Estruturas de Dados

Número de divisores com fatorização em primos

Uma forma ingénua de encontrar o número de divisores de um inteiro positivo n seria percorrer todos os números de 1 até n, e contar quantos deles dividem n.
Contudo, esta abordagem é muito lenta. É possível determinar o número de divisores de n usando os seus fatores primos (a determinação dos fatores primos requer apenas de tempo).
Vamos imaginar que um número é representado como um produto dos seus fatores primos:
Para calcular o número de divisores de n, basta somar 1 a cada expoente e multiplicar esses valores:
Podemos implementar isto de forma semelhante a como obtemos todos os fatores primos de n:
n = ...
p, divisors = 1, 1          # fator primo e número de divisores

while p * p <= n:           # enquanto p <= sqrt(n)
    p += 1                  # Aumenta 1 ao fator primo em cada iteração
    if n % p != 0:          # Não faz nada se n não é divisível por p
        continue
    
    exp = 0                 # contador para o expoente
    while n % p == 0:       # divide tantas vezes quanto possível
        n //= p
        exp += 1
    divisors *= exp + 1     # atualiza o produto

if n > 1:                   # se p > sqrt(n) => n é ele próprio um fator primo
    divisors *= 2           # adiciona n como um divisor com expoente 1
print(divisors)

Desafio: Encontrar o número de divisores de n

Dado um inteiro n, pretende-se encontrar o número de divisores de n.

Entrada

A primeira linha da entrada contém um único inteiro n (2 ≤ n ≤ ).

Saída

O programa deve imprimir o número de divisores de n.

Exemplos

Entrada
Saída
8
4
17
2
2048
12
48
10
Bónus: Por que razão somar 1 a cada expoente e depois multiplicar estes valores resulta no número total de divisores de n?
A explicação intuitiva para a fórmula que determina o número de divisores de n assenta no facto de esses divisores serem formados pelas várias combinações dos seus fatores primos. O expoente de cada fator indica o número de vezes que ele pode aparecer no produto que gera um divisor de n. Ao somarmos 1 a cada expoente, passamos também a incluir a utilização de 0 desse fator, o que abrange divisores como o próprio n e o 1. O resultado de multiplicar todos os valores de (expoente + 1) para cada fator primo é o total de combinações possíveis de todos os fatores, ou seja, o número 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