本文共 1797 字，大约阅读时间需要 5 分钟。

Problem Description
A positive proper divisor is a positive divisor of a number n, excluding n itself. For example, 1, 2, and 3 are positive proper divisors of 6, but 6 itself is not.

Peter has two positive integers n and d. He would like to know the number of integers below n whose maximum positive proper divisor is d.

Input
There are multiple test cases. The first line of input contains an integer T (1≤T≤106), indicating the number of test cases. For each test case:

The first line contains two integers n and d (2≤n,d≤109).

Output
For each test case, output an integer denoting the answer.

Sample Input
9
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
100 13

Sample Output
1
2
1
0
0
0
0
0
4

Source
BestCoder Round #84
思路，要想找1到n里最大因子是d的个数，可以变换一下式子，d<dx<n，这样就变成了求满足条件的x的个数，同时dx还必须满足d是它的最大因子，那么我们可以设d的最小素因子为y，答案就一定是【2，min（（n-1）/d，m）】区间的素数个数，素数打表就好了。

#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn=5e5+100;int n,d,prime[maxn],top=0,pos[maxn],isprime[maxn]={   0};void Prime(int n){       for(int i=2;i<=n;++i)    {           if(!isprime[i]) prime[++top]=i,pos[i]=pos[i-1]+1;        else pos[i]=pos[i-1];         for(int j=1;j<=top;++j)        {               if(i*prime[j]>n) break;            isprime[i*prime[j]]=1;            if(i%prime[j]==0) break;        }    }}int main(){       int T;    Prime(maxn);    scanf("%d",&T);    while(T--)    {           scanf("%d %d",&n,&d);        if(d>=(n+1)/2){               printf("0\n");continue;        }        int temp=(n-1)/d,flag=0;        for(int j=1;j<=top&&prime[j]*prime[j]<=d;++j)        {               if(d%prime[j]==0)            {                   flag=1;                temp=min(temp,prime[j]);                break;            }        }        if(!flag) temp=min(temp,d);        printf("%d\n",pos[temp]);    }}