求区间[L,R]的整数中哪一个的正约数最多。
一个数因数分解后， 它的约数Cnt = (a[j]+1) 的乘积 ，j是每个因数的个数
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;
const int M=1e5+30;
#define int long long
int b[M],prime[M],tot,n;
void init(int top){
memset(b,1,sizeof b);
b[1]=0;
int i,j;
for(i=2;i<=top;i++){
if(b[i]) prime[++tot]=i;
for(j=1;j<=tot&&i*prime[j]<=top;j++){
b[i*prime[j]]=0;
if(i%prime[j]==0) break;
}
}
}
int Count(int x){
int i,s=1,cnt;
for(i=1;prime[i]*prime[i]<=x;i++){
cnt=1;
if(x%prime[i]==0){
while(x%prime[i]==0) x/=prime[i],cnt++;
s*=cnt;
}
}
if(x>1) s*=2;
return s;
}
signed main(){
int tes,L,R;
init(1e5);
cin>>tes;
while(tes--){
cin>>L>>R;
int ans=0,id=0;
for(int i=L;i<=R;i++){
int x =Count(i);
if(x>ans) ans=x,id=i;
}
printf("Between %d and %d, %d has a maximum of %d divisors."
,L,R,id,ans);
puts("");
}
}