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
http://blog.csdn.net/acm_cxq/article/details/52012725
#include<stdio.h>
#include<math.h>
#define N 50000
int x[N],prime[N],tmp=0;
void isPrime()
{
for(int i=0;i<=N;i++) x[i]=1;
x[0]=x[1]=0;
for(int i=2;i<N;i++)
{
if(x[i])
{
prime[tmp++]=i;
for(int j=2*i;j<N;j+=i)
x[j]=0;
}
}
}
int main(){
int n;
scanf("%d",&n);
isPrime();
while(n){
int s,num,sum=0;
scanf("%d %d",&s,&num);
for(int i=0;i<tmp;i++){
if(prime[i]*num>=s) break;
sum++;
if(prime[i]>num) break;
}
printf("%d\n",sum);
n--;
}
return 0;
}