# PBinfo #1394 – devt – Rezolvare C++

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

## Enunț

Enunț
Într-o zi, Gigel a găsit pe masa tatălui său o foaie A4 pe care era trecut șirul denumit “devt” sub forma 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, ... , n. Dedesubtul acestui șir găsește un text alcătuit din k întrebări de forma a, b cu semnificația “Câte numere din acest șir se află în intervalul [a,b]?”.

Cerința
Ajutați-l pe Gigel să răspundă corect la toate cele k întrebări.

Date de intrare
Fișierul de intrare devt.in conține pe prima linie numerele naturale n și k, iar pe următoarele k linii numerele a, b cu semnificația din enunț.

Date de ieșire
Fișierul de ieșire devt.out va conține k linii, pe fiecare linie i aflându-se un număr natural, reprezentând răspunsul întrebării i. 

Restricții și precizări

0 ≤ a ≤ b ≤ n ≤ 100.000
1 ≤ k ≤ 5000
n aparține șirului devt

Exemplu:
devt.in

25 5
3 7
12 20
3 4
16 24
12 24
devt.out

2
6
1
6
9
Explicație
În intervalul [3,7] se află 2 numere din șir. 
În intervalul [12,20] se află 6 numere din șir.
În intervalul [3,4] se află 1 număr din șir.
În intervalul [16,24] se află 6 numere din șir.
În intervalul [12,24] se află 9 numere din șir.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream in("devt.in");
ofstream out("devt.out");
int rez[100001], v[100001];
int long long n, k, i, j, z;
int main() {
    in >> n >> k;
    v[1] = 1;
    for (i = 2; i <= n; i++)
        if (v[i] != 1)
        for (j = i * i; j <= n; j = j + i) 
        	v[j] = 1;
    for (i = 1; i <= n; i++) {
        rez[i] = rez[i - 1];
        if (v[i] == 1)
            rez[i]++;
    } for (z = 1; z <= k; z++) {
        in >> i >> j;
        if (v[i] == 1)
            out << rez[j] - rez[i] + 1 << "\n";
        else out << rez[j] - rez[i] << "\n";
    } return 0;
}
```

## Resurse

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