Number of divisors with prime factorization
A naive approach to finding the number of multiples of a positive integer
n is by looping over all the numbers from 1 to n inclusive and counting the number of values that divide n.Yet, this approach is very slow. It’s possible to find the number of divisors of
n using its prime factors (finding prime factors takes only time). Imagine a number is represented as a product of its prime factors:
We can calculate the number of divisors of
n by taking all the exponents, adding 1 to those, and multiplying the resulting exponents together:This can be implemented very similarly to how we find all the prime factors of
n:n = ...
p, divisors = 1, 1 # prime factor and the number of divisors
while p * p <= n: # while p <= sqrt(n)
p += 1 # Add 1 to the prime factor on each iteration
if n % p != 0: # Do nothing if n is not divisible by p
continue
exp = 0 # counter for the exponent
while n % p == 0: # divide as many times as possible
n //= p
exp += 1
divisors *= exp + 1 # update the product
if n > 1: # if p > sqrt(n) => n is a prime factor itself
divisors *= 2 # add n as a divisor with exponent 1
print(divisors)Challenge: Find the number of divisors of n
Given an integer
n, you are asked to find the number of divisors of n.Input
The first line of the input contains a single integer
n (2 ≤ n ≤ ).Output
The program should print the number of divisors of
n.Examples
Input | Output |
8 | 4 |
17 | 2 |
2048 | 12 |
48 | 10 |
Bonus: Why does taking all the exponents, adding 1 to those, and multiplying the resulting exponents together result in the total number of divisors of n?
The intuition behind the formula for finding the number of divisors of
n comes from considering the number of divisors as the number of combinations of its prime factors. The exponent of each factor is the number of times it can be used in the product that forms the divisor of n. Adding 1 to each exponent allows for including combinations that include 0 of each prime factor, which corresponds to including n itself and 1 as divisors of n. The final result of multiplying the (exponent + 1) of each prime factor together counts the number of combinations of all prime factors and gives the total number of divisors of n.Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB