Deepak and primes

#1

can you please share approach of doing this question

#2

Hey @jatinkumarjk2001
The problem can be easily solved by using Sieve of Eratosthenes. We just need to precompute the sieve and then run our loop for all the test cases and answer all the queries. All the queries will be answered in O(1) complexity as we have already precomputed the sieve for extracting prime numbers.

#3

how to precompute the seive

#4

@jatinkumarjk2001
Following is the algorithm to find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
Initially, let p equal 2, the first prime number.
Starting from p2, count up in increments of p and mark each of these numbers greater than or equal to p2 itself in the list. These numbers will be p(p+1), p(p+2), p(p+3), etc…
Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

#5

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.