### atlasworld's blog

By atlasworld, history, 20 months ago, ,

in problem 27E you are asked to find the smallest positive integer which has exactly n divisors .

how to solve it > >

• +5

 » 20 months ago, # | ← Rev. 3 →   +3 We denote the number of divisors of a number x, as d(x). It can be proven that d(x) = (e 1 + 1)·(e 2 + 1)·...·(e k + 1) , where x = p 1 e 1·p 2 e 2·...·p k e k is the prime factorization of x.We notice that it's optimal for p 1 to be as small as it can be, so it should be equal to 2. We notice the same for p 2, so it should be equal to 3. It is optimal to take the smallest possible prime every time. So we should only take the first k primes. But consider the case where e i = 1 i. We see that if we take more than p k = 41 (approximately), we are way over our limit of 1018 for our answer. So our list of primes should be up to 41.Now we try to construct the desired number by some kind of trial-and-error. As long as we can multiply our current number with the current prime raised to some power e i, we test for this situation, going to the next prime, knowing the current number's divisors and its value. Notice that every prime should not fit more than times in some number X, and we only have about 15 primes, so operations aren't too much.Solution link: 43224863
•  » » 20 months ago, # ^ |   +5 thanks.. charis .. i got it...trying every possibility in brute force way to get the minimum number...ur solution is very clear... :))
•  » » 20 months ago, # ^ |   0 You can bring down the operations even more, considering the fact that e(i)>=e(i+1) in the optimal solution.
•  » » » 20 months ago, # ^ |   +5 Yes, you are right. Holding an extra parameter for e i - 1 and starting e i from there instead of 1. I believe you can also use dp on this idea if you modify it a little, but I don't think it's necessary.