I need help with this problem. I solved it using bruteforce upto n which I think will give TLE in other contests (like long challenges). So I need a better approach. I saw several other solutions which got AC in sqrt(n) time. I know to use it when number is divisible by n. But in this case, the numbers might not be divisible.

Like this,

Say the number is N. Then for each number from 1 to N, you would test if it is divisible by ith number right?

Let the N/x=y, then N/y=x right? Therefore, the answer should be the sum of i and N/i and this would run in O(sqrt(N)).

N/x=y then N/y=x is applicable if N is divisible by x or y which is not the case here.

Consider for n=3;

x=1 y=3

x=2 y=1 // This is the part I can’t find in sqrt(n)

x=3 y=2

So total = 8

If it is divisible then N%x==0

we are using division here, not modulus. What’s your point?