C# – Algorithms – Find n-th divisor of an integer

The Codeforces contests are sometimes more challenging than expected, even for the first problems, which are supposed to be trivial. Well, they are not that trivial. In the 762. edition, the 1. problem was concerning the n-th divisor of an integer.

cs

Pretty much, the task looks like this:

You are given two integers n and k. Find k-th smallest divisor of n, or report that it doesn’t exist.

Divisor of n is any such natural number, that n can be divided by it without remainder.

Input

The first line contains two integers n and k (1 ≤ n ≤ 1015, 1 ≤ k ≤ 109).

Output

If n has less than k divisors, output -1.

Otherwise, output the k-th smallest divisor of n.

It looks difficult, and actually it is. The trick is that there is no known algorithm for getting the n-th divisor. But still, we can think of something better than looping up to the end and checking whether the number passes. Thus, looping up to the square root of the number to check is quite enough. The trick is to add also the numbers, which are found through the looping. (This is better to be seen than explained). E.g., if we have 60 and we start looping with 1,2,3,4, etc up to sqrt of 60 when we reach 1, we add 60 as well to the result list, when we are at 2 – we add 30, at 3 we add 20 etc. Then we sort. And pretty much that is it!

Here comes the code:

Available in GitHub as well.

About

VBA Developer

Tagged with: , ,