Prime queries


Submit solution

Points: 35 (partial)
Time limit: 1.5s
Memory limit: 250M

Author:
Problem type

You are given a list of integers \(a_i\) and you are asked to answer \(q\) queries.

Each query is of the form \(l_i\), \(r_i\) and asks you to count for each prime number \(p, p \in [l_i, r_i]\) the number of integers \(a_i\) that are multiples of \(p\) and output their sum (the sum of counts, not the sum of multiples !).

Input Specification

The first line of the input file contains three integers \(n\) the number of elements \(a_i\) , \(k\) the maximum range and Q the number of queries (\(1 \leq n,k,q \leq 10^6\)).

Then follows one line containing \(n\) integers \(a_i\) (\(1 \leq a_i \leq 10^6\)).

\(Q\) lines will follow, each line consists of two integers \(l_i\) \(r_i\) (\(1 \leq l_i \leq r_i \leq k\)).

Output Specification

For each query output one integer containing the answer to the problem.

Scoring

  • \(n, q, k \leq 10^2\) (20 points).
  • \(q = 1, n \leq 10^3\) (20 points).
  • \(q = 1\) (30 points).
  • No additional constraints (30 points).

Sample Input

3 10 4
6 7 8
1 2
1 3
5 6
1 10

Sample Output

2
3
0
4

Comments

There are no comments at the moment.