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 ≤ 100000
• 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.

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

ifstream fin ("devt.in");
ofstream fout ("devt.out");

int x[100001];
int s[100001];

int main ()
{
    int n,q,a,b;
    x[1]=1;
    fin >> n;
    for (int i=2;i<=n;++i)
        if(x[i]==0)
            for (int j=i+i;j<=n;j=j+i)
                x[j]=1;
    for (int i=1;i<=n;++i)
        s[i]=s[i-1]+x[i];
    fin >> q;
    for (int i=1;i<=q;++i)
    {
        fin>>a>>b;
        fout <<s[b]-s[a-1]<< endl;
    }
    
    fin.close();
    fout.close();
    
    return 0;
}