Volume CXIX (11900-11999)

•  11945 - Financial Management

•  11956 - Brainfuck

•  11957 - Checkers

•  11960 - Divisor Game

•  11965 - Extra Spaces

•  11974 - Switch The Lights

•  11987 - Almost Union-Find

•  11991 - Easy Problem from ...

If we know the prime factorization of a number, we can easily find the number of divisors.

For example, 18 has 6 divisors. If we prime factorize 18, we find that

18 = 2¹ * 3²

We can say that any divisor of 36 should be in the form

2^x * 3^y 

 So, we can say that the number of divisors of 18 is

(1 + 1) * (2 + 1) = 6

So, if a number is factorized as

2^x * 3^y

Then the number of divisors is (x+1) * (y+1). 

Similarly, suppose a number is factorized as 2^x * 3^y * 5^z, so, the total number of divisors is

(x + 1) * (y + 1) * (z + 1)

 Now, the general formula is

If the prime factorization of an integer is

p₁^x1 * p₂^x2 * p₃^x3 * ... * p_n^xn

where, p₁, p₂, ..., p_n are primes, then the number of divisors is

(x₁ + 1) * (x₂ + 1) * (x₃ + 1) * ... * (x_n + 1)

set ans[1]=1 max=max_num_div=1;

for i=2 to 1000000

---- set n = number of divisor of i // find it using method which is describe in above.

---- if n>=max_num_div then set max_num_div=n and max=i

---- set ans[i]= max

For each input n print ans[n]