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.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("eratostene8.in");
ofstream cout("eratostene8.out");

int n,t,s,d,E[10000001], P[10001];
bool F[1000001];

int main(){
    cin >> n >> t;
    for(int i = 1; i <= n; ++i)
        cin >> P[i];
    for(int i = 1; i <= n; ++i){
        E[P[i]]=1;
        if(F[P[i]] == 0){
            for(int j = 2; j * P[i] <= 10000000; ++j)
                E[P[i] * j] = 1;
            F[P[i]] = 1;
        }
    }
    for(int i = 1; i <= 10000000; ++i)
        E[i] = E[i-1] + E[i];
    for(int i = 1; i <= t; ++i){
        cin >> s >> d;
        cout << E[d] - E[s-1] << '\n';
    }
}