SPOJ Q&A

#include<stdio.h>
#define max 100001
#define ull long long int
int pre[max][11];
void presolve()
{
int i,j,temp,k;
for(i=2;i*i<max;i++)
{
if(pre[i][10])
continue;
k=i*i;
for(j=k;j<max;j+=k)
{
if(pre[j][10]==0)
pre[j][10]=1;
}
}

for(i=0;i<max;i++)
{
if(pre[i][10]==0)
{
temp=i;
while(temp)
{
pre[i][temp%10]=1;
temp/=10;
}
}
}
for(i=1;i<max;i++)
{
for(j=0;j<=9;j++)
pre[i][j]+=pre[i-1][j];
}

}

int main()
{
int t,a,b,d;
scanf("%d",&t);
presolve();
while(t--)
{
scanf("%d%d%d",&a,&b,&d);
printf("%d\n",pre[b][d]-pre[a-1][d]);
}
}