@bhishma - How did you create an array of 10^7 elements? I thought of this same thing, but dropped the idea as C++ doesn’t allow creation of int arrays of more than 2*10^6 I think.
That equivalently means that the result for a number ‘n’ is equal to the product of the result of two numbers ‘n1’ and ‘n2’ iff gcd(n1, n2)=1 i.e. they are coprime.
If n1 and n2 are further represented as the product of two coprime numbers, you eventually reach at the numbers that are “powers of a single prime”.
Now the only task is “how to calculate the result for numbers, which are powers of a single prime?”
This is fairly simple and can be done by summing the phi(d).d for every divisor d of that number.
The basic approach for any problem is to think of the possible solution and observing the patterns while keeping the constraints in the mind at the same time.
When you get some approach, think about it and try to prove the correctness, if you’re not able to prove the correctness, try to find a counter example, if you’re not able to find one, never hesitate to implement the approach in long challenges. At the end, long challenge will teach you a lot.