Eratostene8

#include <fstream>
#define N 10000001
using namespace std;
int M[N];

int main()
{
    int n,t;
    ifstream f("eratostene8.in");
    f>>n>>t;
    int np;
    for(int i=1;i<=n;++i)
    {
        f>>np;
        if(M[np]==0)
        {
            int j=1;
            while(np*j<N)
                    M[np*j]=1,++j;
        }
    }
    for(int i=1;i<N;++i)
        M[i]+=M[i-1];
    int s,d;
    ofstream g("eratostene8.out");
    while(t--)
        f>>s>>d,g<<M[d]-M[s-1]<<'\n';
    return 0;
}