time limit exceeded. help me out.
Prime minister visit
Hello @ankit152,
Use prime sieve to first store prime numbers in an array once at the beginning of the program and then for every number between a and b check if it is present in the array. By using sieve you can save time by not repeating the procedure again and again.
In your code, for every value of i you are check if it is prime or not. This takes too much time in case of multiple testcases. To avoid this, declare a boolean array ‘prime’ of size 1000001 and mark 1 at the index of prime numbers and the other numbers as 0. Do this at the start of the program before taking input n,a and b.
Then update your condition in line 14 to if(prime[i]). (Also, declare the array globally)
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.