Đề bài: Chú gấu Tommy và số nguyên tố

Đề bài:

Tommy là một chú gấu dễ thương, rất yêu thích việc học hỏi. Một ngày, Tommy và các bạn học về số nguyên tố. Tuy nhiên, thầy giáo đã đưa ra một bài toán khó và yêu cầu Tommy giải quyết thật nhanh.

Cho một dãy số nguyên dương ~ x_1, x_2, \dots, x_n ~ và ~ m ~ truy vấn. Mỗi truy vấn là hai số nguyên ~ l_i ~ và ~ r_i ~. Với mỗi truy vấn, tính tổng:

• ~ S(l_i, r_i) ~ là tập hợp các số nguyên tố trong đoạn ~[l_i, r_i]~,
• ~ f(p) ~ là số lượng các số ~ x_k ~ trong dãy ban đầu chia hết cho ~ p ~.

Yêu cầu: Trả lời kết quả cho từng truy vấn.

Input:

• Dòng đầu chứa số nguyên ~ n ~ ~(1 \leq n \leq 10^5)~,
• Dòng thứ hai chứa ~ n ~ số nguyên dương ~ x_1, x_2, \dots, x_n ~ ~(2 \leq x_i \leq 10^7)~,
• Dòng thứ ba chứa số nguyên ~ m ~ ~(1 \leq m \leq 50,000)~,
• Mỗi dòng trong ~ m ~ dòng tiếp theo chứa hai số nguyên ~ l_i ~ và ~ r_i ~ ~(2 \leq l_i \leq r_i \leq 2 \times 10^9)~.

Output:

• Gồm ~ m ~ dòng, mỗi dòng chứa một số nguyên là kết quả của truy vấn.

Sample Input 1:

6
5 5 7 10 14 15
3
2 10
3 12
4 4

Sample Output 1:

9
7
0

Giải thích:

• Truy vấn 1: ~ l = 2, r = 10 ~:

  • Số nguyên tố trong đoạn ~[2, 10]~: {2, 3, 5, 7}.
  • ~ f(2) + f(3) + f(5) + f(7) = 2 + 1 + 4 + 2 = 9 ~.

• Truy vấn 2: ~ l = 3, r = 12 ~:

  • Số nguyên tố trong đoạn ~[3, 12]~: {3, 5, 7, 11}.
  • ~ f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7 ~.

• Truy vấn 3: ~ l = 4, r = 4 ~:

  • Không có số nguyên tố nào trong đoạn ~[4, 4]~, kết quả là ~ 0 ~.