Getting TLE for PRIME1 on SPOJ?

Can anyone please tell me whats’s the reason for TLE and how can i optimize it?
Here’s link to problem
and here’s my solution
Thank you for helping.

First go through this algo…even this will not suffice for this problem…u will have to go through segmented sieve!!!

1 Like

Instead of checking the divisibility of every number from 1 to i, you only have to go up to the square root of i. This can be checked using j * j <= i. Further, you can cut this in half by checking if i is divisible by 2 and then checking if i is divisible by odd numbers starting with 3. Also, if you find that i is divisible by any number other than 1 and itself, then you know it is not a prime and can immediately leave the loop. (I just happened to solve this problem on SPOJ yesterday :slight_smile: ).

1 Like

I’m not able to understand the implementation of segmented sieve.How can i modify sieve of Eratosthenes into segmented sieve?I got the algorithm,but finding it difficult to code it.Can it be coded without use of vector and Queue.

For implementation of sieve u can search it here…

Yes it can be done without the use of vector and queue!!!

If u want to see some implementations of segmented sieve then you can check then out here…