LightOj 1109 - False Ordering

#include <bits/stdc++.h>
using namespace std;
#define n 1000005
bool a[n];
long long int k=1;
long long int twin[n],i,j,t;
bool compare(const pair<long long int,long long int>&x, const pair<long long int, long long int>&y )
{

return (x.second<y.second);

}
void sieve()
{
long long int i,j;
a[0]=a[1]=1;
for(i=4;i<=n;i=i+2)
{
a[i]=1;
}
for(i=3;i<=sqrt(n);i=i+2)
{
for(j=i*i;j<=n;j=j+2*i)
{
a[j]=1;        //3*3, 3*5,3*7.....
}
}
for(i=2;i<=n;i++)
{
if(a[i]==0)
{
twin[k]=i;
k++;
}
}

}

long long int nod(long long int q)
{
long long int g,c,r,s,h,l,m;
m=q;
r=1;
h=0;
for(g=1;g<=k && twin[g]<=sqrt(m);g++)
{
c=0;
if(m%twin[g]==0)
{

while(m%twin[g]==0)
{
c++;
m=m/twin[g];
if(m==0 || m==1)
{
break;
}

}
s=c+1;
r=r*s;
}

}
if(m!=1)
{
r=r*2;    //for prime numbers there are only 2 divisors.
}

return r;

}

int main()
{
long long int cnt,u,y,w,z,in,b[1005];
//freopen("1109in.txt","r",stdin);
//freopen("1109out.txt","w",stdout);
vector<pair<long long int,long long int> >v;
vector<long long int>res;
sieve();
for(z=1000;z>=1;z--)
{
cnt=nod(z);
//cout<<z<<" "<<cnt<<endl;
v.push_back(make_pair(z,cnt));
}
stable_sort(v.begin(),v.end(),compare);
vector<pair<long long int,long long int> >::iterator p;

for(p=v.begin();p!=v.end();p++)
{
in=p->first;
res.push_back(in);

}
for(z=0;z<res.size();z++)
{
b[z]=res[z];
}
scanf("%lld",&t);
for(w=1;w<=t;w++)
{
scanf("%lld",&u);
printf("Case %lld: %lld\n",w,b[u-1]);

}

return 0;
}