I am using sieve of erastothenes to generate primes upto sqrt(10pow9),and then using those primes to generate primes of given segment but its giving TLE!! why?
whats going wrong here?
http://www.codechef.com/viewsolution/6862618
Your approach is extremely slow. After generating the primes, lets say you are given about 100 (for example, should be more in real test data) primes in the interval. For all the primes, you are dividing the primes with all the primes below its sqrt which is huge. Instead, you can use segmented sieve to check their primality and skip the divisions.
Check out this link for segmented sieve implementation and u can use my code as reference.