How to solve this question of finding the number of primes in a range.? We need to make a segmented sieve for every range but then also I am getting TLE in 4 cases.
This is how i approached the problem. I made a prime sieve for square_root(max(n)) . Then for every range given I made a segmented sieve of size (n-m+1) and then counted the number of primes as explained in the lecture.
Is there any way we can precompute a segmented sieve. ? How to reduce the time complexity ?
Using segmented sieve efficiently
You have to iterate over multiples of primes only for every range.
Refer this for better understanding -:
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.