Getting TLE for PRIME1 on SPOJ?

Can anyone please tell me whats’s the reason for TLE and how can i optimize it?
and here’s my solution http://ideone.com/3atoMi
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 ).

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…geeksforgeeks.org

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…codechef.com/problems/PRIME1