Algorithms and Data Structures

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: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

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