Rezolvare PBinfo #3319

Cerința

Se dau n numere naturale prime. Pentru t perechi de numere naturale s şi d să se afle câte numere naturale din intervalul [s,d] sunt divizibile prin cel puţin unul dintre cele n numere prime.

Date de intrare

Fișierul de intrare eratostene8.in conține pe prima linie numerele n şi t, pe a doua linie cele n numere prime, iar pe următoarele t linii câte o pereche de numere s şi d.

Date de ieșire

Fișierul de ieșire eratostene8.out va conține pe linia i răspunsul la întrebarea i, pentru orice i de la 1 la t.

Restricții și precizări

• 1 ≤ n ≤ 10.000
• 1 ≤ t ≤ 100.000
• 1 ≤ s ≤ d ≤ 10.000.000
• numerele prime sunt mai mici sau egale cu 1.000.000

Exemplu:

eratostene8.in

2 3
2 3
1 5
4 6
5 20

eratostene8.out

3
2
10

Explicație

Numerele prime date sunt 2 şi 3. În intervalul [1,5] sunt 3 numere divizibile cu 2 sau 3, în intervalul [4,6] sunt 2 numere divizibile cu 2 sau 3, iar în intervalul [5,20] sunt 10 numere divizibile cu 2 sau 3.