题目
给定n和d，都是10的9次方以内，求1到n里面有几个数最大因数是d？1000000组数据。
解：求出d的满足p[i]*d<n的最小质因数是第几个质数。即为答案。
#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);
}
}
原文：http://www.cnblogs.com/flipped/p/5699986.html