Can anyone tell me the logic of the code from AtCoder?

Suppose kk is a prime, then, the answer is always kk. If kk is composite, remember that if a divisor an integer nn is less than or equal to n−−√n, the other divisor is greater than or equal to n−−√n. The solution uses that idea.

The limit is 2⋅1062⋅106, you can get a better limit by figuring out the last prime smaller than 106106(which is 999983999983) and multiply by 22. Why multiply by 22? Because we can get a square of that prime as an input for kk(which means that the answer would be prime∗2prime∗2). Check the answer for k=1999966k=1999966 with limit=106limit=106 to get what I mean and why the limit should be at least 19999661999966.

Here is an alternative approach. Suppose k is 1792. Convert 1792 into 2^8 * 7^1. It is clear that n needs to be at least 7 in order to cover the 7, but what is the n required to provide eight 2s? Let's count: 2 provides one 2. 4 provides two 2s. 6 provides one 2. 8 provides three 2s. Now we have (1+2+1+3 = 7) 2s. We still need one more. 10 provides one 2. Now we have eight 2s. This means n==10 is the max n needed. The other factor found earlier is n==7 but 7 is less than 10. So, the answer is 10.

Edit: Just realized OP was referring to a particular submission.