What approach should i use can anyone explain with the help of an example?
You may approach the problem in this way:
The given function is:
G(N) = F(1) + F(2) + ... + F(N)
Now,
How many numbers up to N, that has 1 has a divisor? - N / 1
Therefore, 1 contributes - 1 * (N / 1) to G(N).
How many numbers up to N, that has 2 has a divisor? - N / 2
Therefore, 2 contributes - 2 * (N / 2) to G(N).
How many numbers up to N, that has 3 has a divisor? - N / 3
Therefore, 3 contributes - 3 * (N / 3) to G(N).
How many numbers up to N, that has 4 has a divisor? - N / 4
Therefore, 4 contributes - 4 * (N / 4) to G(N).
.
.
.
.
How many numbers up to N, that has k(<= N) has a divisor? - N / k
Therefore, k contributes - k * (N / k) to G(N).
How many numbers up to N, that has N has a divisor? - N / N
Therefore, N contributes - N * (N / N) to G(N).
So, now you can find out G(N) by simply using a for
loop and summing up the contributions of each of the numbers up to N.