【HDU 5750】Dertouzos（数学）

#include<cstdio>
#define N 100002
int t,n,d,pr[N],p[N],num;
int main(){
    for(int i=2;i<N;i++)if(!pr[i]){
        for(int j=i+i;j<N;j+=i)
            pr[j]=1;
        p[++num]=i;
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&d);
        int k=1;
        for(int i=1;i<=num&&p[i]<=d&&p[i]*d<n;i++){
            if(d%p[k]==0)
                break;
            k++;
        }
        if(p[k]>d||p[k]*d>n)k--;
        printf("%d\n",k);
    }
}