149. Primes in a Range
MediumSievePrefix Sum
Answer q queries: how many primes lie in [l, r]?
Input format
Line 1: q Next q lines: l r
Output format
One count per line.
Example 1
Input
3 1 10 11 19 20 22
Output
4 4 0
Example 2
Input
1 1 1000000
Output
78498
Constraints
1 ≤ q ≤ 10⁵ 1 ≤ l ≤ r ≤ 10⁶
Read input from standard input and print the answer to standard output. Your code is judged against 5 test cases, most of them hidden.
Loading the MyLoginn IDE…