Help me solve the task, plz!

Question

Find the number of repetitions of numbers k in the Pythagorean table n*n? For example input: k =12, n=6 . Output: 4 .

P.s (1 ≤ 𝑛 ≤ 10^5; 1 ≤ 𝑘 ≤ 10^9) iterating over an array is to slow.

Answer 1

One possible strategy that came to my mind would be to check for all numbers up to the square root of 'k' if they are divisors of it. If a number 'i' is a factor of 'k', 'k' will appear in the table if 'i' and another factor 'j' = 'k' / 'i' both are smaller or equal to 'n', in which case you can just add two to some counter variable.

For odd numbers of 'k', you could further optimize this by only checking odd factors.

If 'k' is a square number, it will have one additional factor, its square root. I would test this after the loop to minimize the amount of if-statements inside the loop.

No idea how this performs against time restraints though, which you seem to have, so if there are better approaches others can come up with, I'm looking forward to hearing those.