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.
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=2 y=1 // This is the part I can’t find in sqrt(n)
So total = 8
If it is divisible then N%x==0
we are using division here, not modulus. What’s your point?