RGCDQ

2
2 3
3 5

1
1

/*
dp[i][j]记录小于等于i的含有不同质因子的个数

*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define bug printf("hihi\n")

#define eps 1e-8
typedef __int64 ll;

using namespace std;


#define INF 0x3f3f3f3f
#define N 1000005
#define M 8

int dp[N][M];
int pri[9]={2,3,5,7,11,13,17,19,23};
int a[N];

void inint()
{
    int i,j;
     for(i=2;i<N;i++)
        if(!a[i])
         for(j=1;i*j<N;j++)
            a[i*j]++;

   for(i=1;i<M;i++)
      for(j=1;j<N;j++)
         if(a[j]==i) dp[j][i]=dp[j-1][i]+1;
           else  dp[j][i]=dp[j-1][i];
}

int main()
{
   inint();
   int i,j,t;
   scanf("%d",&t);
   int le,ri;
   int ans;
   while(t--)
   {
       scanf("%d%d",&le,&ri);

       for(i=8;i>=1;i--)
       {
           if(dp[ri][i]-dp[le-1][i]>1)
           {
               ans=i;
               break;
           }
           for(j=i+i;j<8;j+=i)
           {
               if(dp[ri][j])
               {
                   ans=i;
                   i=10;
                   break;
               }
           }
       }
       printf("%d\n",ans);
   }
   return 0;
}

hdu 5317 RGCDQ

原文：http://blog.csdn.net/u014737310/article/details/47110213