SỐ NGUYÊN TỐ

Nguồn: Chuyên Hoàng Văn Thụ - Hòa Bình

Cho dãy số nguyên x₁, x₂, …, x_N và hàm f(p) là số lượng các phần tử thuộc dãy x chia hết cho p.

Cho M truy vấn, mỗi truy vấn cho hai số nguyên l_i, r_i. Bạn phải trả lời câu hỏi: Tính tổng:

 , ở đây S(l_i, r_i) là tập các số nguyên tố thuộc đoạn [l_i,r_i].

INPUT:

·         Dòng đầu tiên chứa giá trị N (1 ≤ N ≤ 10⁶)

·         Dòng hai chứa N số nguyên x₁, x₂, …, x_N (2 ≤ x_i ≤ 10⁵)

·         Dòng ba chứa giá trị M (1 ≤ M ≤ 5*10⁴)

·         M dòng tiếp theo, mỗi dòng chứa hai số l_i, r_i (2 ≤ l_i ≤ r_i ≤ 2*10⁹)

OUTPUT:

·         Gồm M dòng, mỗi dòng là câu trả lời của truy vấn tương ứng của INPUT.

Ví dụ:

PRIME.INP	PRIME.OUT
6 5 5 7 10 14 15 3 2 11 3 12 4 4	9 7 0

Giải thích:

·         Tại truy vấn 1: l = 2, r = 11:

Ta cần tính f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9.

·         Tại truy vấn 2: l = 3, r = 12:

Ta cần tính f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7

·         Tại truy vấn 3: l = 4, r = 4: không có số nguyên tố nào thuộc đoạn [l,r], nên kết quả truy vấn bằng 0

* Chú ý:

·         40% test 1 ≤ N, M ≤ 100; 1 ≤ l_i ≤ r_i ≤ 1000

·         40% test tiếp theo 1 ≤ N, M ≤ 1000; 1 ≤ l_i ≤ r_i ≤ 1000

·         20% test còn lại 1 ≤ N ≤ 10⁶, 2 ≤ x_i ≤ 10⁵, 1 ≤ M ≤ 5*10⁴, 2 ≤ l_i ≤ r_i ≤ 2*10⁹

 Test - Code - Solution - đề (word)