Help needed SPOJ VECTAR8

question:- https://www.spoj.com/problems/VECTAR8/

i am getting tle in this question…how can i improve my solution…

my solution:- https://www.spoj.com/submit/VECTAR8/id=25889665

Refer this link:

even i have used sieve of eratostheness but problem is somewhat related to precomputation.
i am not getting that part.

Actually you have to use an array to store the answer for each input n…
Exactly same as we do for printing nth fibonacci number using DP, we do precomputation of all terms initially, and print array[n] for each test case.

thanks a lot brother your advice helped a lot for me.

now i am able to compute in O(1)
but now only problem left is that my code is giving wrong answer for input 10^6 and for rest of the input its working fine…
pls check my code and tell my mistake