Can anyone please tell me whats’s the reason for TLE and how can i optimize it?
Here’s link to problem http://www.spoj.com/problems/PRIME1/
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