# PBinfo #3319 – Eratostene8 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

## Cod sursă C++

```cpp
#include <fstream>
#define N 10000000
using namespace std;
ifstream f("eratostene8.in");
ofstream g("eratostene8.out");
int v[N+1];
int n, t, i, j, s, d, p;
int main()
{
    f >> n >> t;
    for(i = 1; i <= n; i++){
        f >> p;
        if(v[p]==0){
            v[p] = 1;
            j = p + p;
            while(j <= N){
                v[j] = 1;
                j = j + p;
            }
        }
    }
    for(i = 1; i <= N; i++)
        v[i] += v[i-1];
    for(i = 1; i <= t; i++){
        f >> s >> d;
        g << v[d]-v[s-1] << "\n";
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3319)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3319/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3319/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)