in this question, why are we using sieve in O(10^7) time and the checking whether it is prime or not by iterating through the primes array.
won’t it be faster if we just check all the numbers between 2 to sqrt(N) and that wpuld do our work in just O(Sqrt(N)) time?
Why do we need sieve
@alankrit.agr99
If you only had to check for one or two numbers , the square root method is better. However if you had to check for multiple numbers repeatedly , sieve is going to much much better.
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.