Range Prime Count

Difficulty: 1300 5000 ms 128 MB

prefix-sum

Answer Q queries: for each range [l, r], count how many elements are prime.

Input: the first line has N and Q; the second line has the array; each next line has l and r.

Output: one count per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• 1 ≤ a_i ≤ 10⁶

Sample Tests

5 2
2 3 4 5 6
1 5
2 4

3
2

1 1
7
1 1

1

Read the Editorial