Spoj Solution :NFACTOR - N-Factorful

#include <bits/stdc++.h>
#define pb push_back
#define Max 1000002
#define lim 1000006
using namespace std;
typedef long long ll;
bool mark[Max];
vector<int>prime,fc;
void sieve()
{
    for(int i=3; i<=sqrt(Max); i+=2)
    {
        if(!mark[i]) for(int j=i*i; j<Max; j+=i) mark[j]=true;
    }
    prime.pb(2);
    for(int i=3; i<Max; i+=2) if(!mark[i]) prime.pb(i);
}
int fac[1000001];
vector<int>vc[1000001];
vector<int>:: iterator l,h;

int ttt(int n)
{
    int cnt=0;
    fc.clear();
    for(int i=0; prime[i]*prime[i]<=n; i++)
    {
        if(n%prime[i]==0)
        {
            while(n%prime[i]==0)
            {
                n/=prime[i];
            }
            fc.pb(prime[i]);
        }
    }
    if(n>1)
    {
        fc.pb(n);
    }
    cnt = fc.size();
    return cnt;
}

int main()
{
    //   freopen("input.txt","r",stdin);
    sieve();
   // cout<<prime.size()<<endl;
    for(int i=2; i<(Max); i++)
    {
        fac[i]=ttt(i);
    }

    for(int i=2; i<1000003; i++)
    {
        int x=fac[i];
        if(x==0) x=1;
        if(x<11) vc[x].pb(i);
    }
    // cout<<vc[1].size()<<endl;
    // cout<<vc[2].size()<<endl;
    vc[1].pb(0);
    int test;
    scanf("%d",&test);
    while(test--)
    {
        int a,b,n,c=0;
        scanf("%d %d %d",&a,&b,&n);
        if(a>b)swap(a,b);

        if(n==0)
        {
            if(a==1) puts("1");
            else puts("0");
            continue;
        }
        if(vc[n].size()==0)
        {
            puts("0");
            continue;
        }
        l=lower_bound(vc[n].begin(),vc[n].end(),a);
        h=upper_bound(vc[n].begin(),vc[n].end(),b);
        // cout<<*l<<" "<<*h<<endl;
        printf("%d\n",h-l);

    }

    return 0;
}