Dertouzos

题意：

有中文，不说。

题解：

我看了别人的题解，还有个地方没懂， 为什么是 if(d%prime[i]==0) break; ？

代码：

#include <bits/stdc++.h>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long ll;

#define PU puts("");

#define PI(A) printf("%d\n",A)

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d%d",&(N),&(M))

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 40000 + 9 ;

int prime[MAXN];

bool is_prime[MAXN];

int sieve(int n)

{

    int p=0;

    for (int i=0;i<=n;i++) is_prime[i]=true;

    is_prime[0]=is_prime[1]=false;

    for (int i=2;i<=n;i++){

        if (is_prime[i]){

            prime[p++]=i;

            for (int j=2*i;j<=n;j+=i) is_prime[j]=false;

        }

    }

    return p;

}

int main()

{

    int K=sieve(MAXN);

    int T;

    SI(T);

    while(T--)

    {

        int n,d;

        SII(n,d);

        int ans=0;

        for (int p=0;p<K;p++)

        {

            if (prime[p]*d>=n) break;

            ans++;

            if (d%prime[p]==0) break;

        }

        PI(ans);

    }

    return 0;

}