Given an array of N integers and another array R containing Q queries(of l and r). Answer all Q queries asking the number of primes in the subarray ranging from l to r (both inclusive).
Note: A is 0-based but the queries will be 1-based.
Example 1:
Input:
N=5,Q=3
A={2,5,6,7,8}
R={{1,3},{2,5},{3,3}}
Output:
2 2 0
Explanation:
There are 2 primes in the range [1,3],
which are 2 and 5.
There are 2 primes in the range [2,5],
which are 5 and 7.
There are no primes in the range [3,3].
Example 2:
Input:
N=5,Q=3
A={1,2,3,4,5}
R={{1,4},{2,5},{2,3}}
Output:
2 3 2
Explanation:
There are 2 primes in range [1,4],
which are 2 and 3.
There are 3 primes in the range [2,5],
which are 2,3 and 5.
There are 2 primes in the range [3,3],
which are 2 and 3.
Your Task:
You don't need to read input or print anything. Your task is to complete the function primeRange() which takes the two numbers N and Q as well as the two arrays A and Q as input parameters and returns the answers of all Q queries.
Expected Time Complexity:O(Max(A[i])*Log(Log (Max(A[i]) )))
Expected Auxillary Space:O(Max(A[i]))
Note: Max(A[i]) represents the maximum value in the array A
Constraints:
1<=N,Q,A[i]<=10^{6}
1<=l<=r<=N

见题面

见题面