PRCN16A - Editorial

PROBLEM LINK:

Practice
Contest

Editorialist: Rounaq Jhunjhunu Wala

DIFFICULTY:

EASY

PREREQUISITES:

Factors

PROBLEM:

Given a number N, we need to find the sum of all factors of N.

EXPLANATION:

This is a very common problem of number theory. The easiest approach to this is to simply loop from 1 to N and add all the numbers which are the factors of N.

ans = 0
for i = 1 to N
  if N%i == 0
    ans = ans + i
print ans

The above approach works, but it is O(N), so it will give a TLE result. We can do the same in O(\sqrt{N}) time complexity.
We know that for any factor i of N, there is a corresponding factor \frac{N}{i} (if i \neq \sqrt{N}). Now, if we take the smaller of \{i,\frac{N}{i}\}, the value would be atmost \lfloor{\sqrt{N}}\rfloor, because if both factors are greater than this quantity, then their product is greater than N, which is not possible.
The observation above gives us the required algorithm:

ans = 0
for i = 1 until i*i <= N
  if N%i == 0
    ans = ans + i
    if i != N/i:
      ans = ans + N/i
print ans

The if check is to handle the case when we get i as the perfect square root of N, in which case only i should be added.

//