Getting TLE for some test cases

#1

I used the simple segmented sieve method. I calculated primesieve upto 10^5 as the constraint of b is 10^9. Any insights as to why I may be getting TLE for some test cases.

#2

@a_krisna22 For testing any number bigger then 10^5 you will need it to divide it with all the prime numbers less then its square root , now if all number are bigger than 10^5 we will have some complexity of around (10^8 or even 10^10 ) that is why it would result in TLE.
If this solves your doubt mark it as resolved.

#3

please tell the line of code where I need to make the change. And also what’s the need for checking of numbers greater than 10^5. Arent

#4

aren’t we simply meant to check upto 10^5 in the sieve and then check the corresponding multiples in the segment sieve

#5

@a_krisna22 we need to apply segmented sieve only.


Here is a code for reference.
You can provide your code in Coding Blocks IDE in case of any doubt.
If this resolves your doubt mark it as resolved.

#6

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.