I'v tried to solve this problem from 4 or 5 days, but the only solution that I'v wrote finish running in 84 seconds using Segmented Sieve.

So is there any hints or resources to start working on the correct solution?