Math Primes and the sieve
97. Count Primes in a Range
You are given a list of queries. Each query is a pair [left, right] and asks how many prime numbers
lie between left and right, both ends included.
Return an array answer with one entry per query, in the order the queries are given: answer[i] is the
count that queries[i] asks for.
A number is prime when it is greater than 1 and its only divisors are 1 and itself. So 2, 3, 5 and 7 are prime, while 1, 4 and 9 are not.
Example 1
Input: queries = [[1, 10], [10, 20], [7, 7], [24, 28]]
[4,4,1,0]Explanation: The primes up to 10 are 2, 3, 5 and 7. From 10 to 20 they are 11, 13, 17 and 19. [7, 7] holds just
7, which is prime, and no number from 24 to 28 is prime.
Example 2
Input: queries = [[1, 1], [2, 2], [1, 2], [2, 3]]
[0,1,1,2]Explanation: 1 is not prime, so [1, 1] holds none. 2 is the smallest prime, so [2, 2] and [1, 2] hold one
each, and [2, 3] holds 2 and 3.
Example 3
Input: queries = [[1, 5000000],
[4999900, 5000000],
[1, 1000000]]
[348513,7,78498]Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ queries.length ≤ 105queries[i] = [left, right]1 ≤ left ≤ right ≤ 5 × 106
Clarifying questions
What you would ask an interviewer before writing any code.