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.

I found this problem in -Morass- blog Link . You can visit it , I am confident that you will find it useful.

You can implement a segmented sieve of Eratosthenes.

why so serious? I believe https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html#toc-tgt-6 is more than enough for this problem

For this problem you can do a lot of optimisation.

`r`

and`c`

. When we get next prime number we increment`++c`

. If`c`

becomes greater than`r`

we do`++r, c = 1`

. So no need insqrt().^{8}] or 12M in total (and no need in supporting the prime list). Also you can try linear sieve or segmented sieve (the codes can be found in this blog entry).UPD: One more fast sieve you can find here. I did not test all mentioned sieves on this problem, sorry.

Alas, it turns out that a solution with $$$sqrt()$$$ and binary search is slightly faster than a solution with above optimizations. The problem can be solved by means of correctly written wheel sieve. Here is the code for the sieve with the base $$$ ( 2, 3, 5, 7 ) $$$ which is fast enough to evade TLE:

Wheel sieve