I have been trying to solve this problem for last few days . Here is the Problem link SPOJ PTRI .
I have used Linear sieve , but the limit is so high that it is getting TLE in O(N) . I have tried it with sieve of aktin also. But still got TLE . Please help me to solve this one.