反素数

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 4142    Accepted Submission(s): 2396

Problem Description

反素数就是满足对于随意i(0<i<x),都有g(i)<g(x),(g(x)是x的因子个数),则x为一个反素数。如今给你一个整数区间[a,b],请你求出该区间的x使g(x)最大。

 

Input

第一行输入n,接下来n行測试数据

输入包含a,b, 1<=a<=b<=5000,表示闭区间[a,b].

 

Output

输出为一个整数,为该区间因子最多的数.假设满足条件有多个,则输出当中最小的数.

 

Sample Input

3 2 3 1 10 47 359

 

Sample Output

2 6 240

#include
     
       int s[5010]={0,1,2,2};void f(){    int i,j;    for(i=4;i<5010;i++)    {        for(j=2;j<=i/2;j++)//i/2表示最大公约数         //for(j=2;j*j<=i;j++)        if(i%j==0)  s[i]++;        s[i]+=2;    }}int main(){	f();    int n,a,b,i,max,t;    scanf("%d",&n);    while(n--)    {        scanf("%d %d",&a,&b);        t=a;        max=0;        for(i=a;i<=b;i++)        {            if(s[i]>max)             {                  max=s[i];                t=i;            }        }        printf("%d\n",t);    }    return 0;}