UVA 294 Divisors ( FZU 1051, UVALive 5595, Regionals 1994 >> Europe - Southwestern )

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / hackerrank / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

vector<int>prime, power;
int status[MX], pl;
void primeGenerator(int n)
{
    int sq=sqrt(n);
    prime.push_back(2);
    for(int i=3;i<=sq;i+=2)
        if(!status[i])
            for(int j=i*i;j<n;j+=i+i)
                status[j]=1;

    for(int i=3;i<n;i+=2)
        if(!status[i])
            prime.push_back(i);
    pl=prime.size();
return;
}

void findPower(int n)
{
    int sq=sqrt(n);
    for(int i=0;prime[i]<=sq;i++)
    {
        int cnt=0;
        while(n%prime[i]==0)
        {
            cnt++;
            n/=prime[i];
        }
        if(cnt)
        {
            sq=sqrt(n);
            power.push_back(cnt);
        }
    }
    if(n!=1) power.push_back(1);
return;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, tc, kk=1, l, u;
    string s;
    cin>>tc;
    primeGenerator(MX-5);
    while(tc--)
    {
        cin>>l>>u;
        if(l>u) swap(l, u);
        int mx=0, id=0;
        for(int i=l;i<=u;i++)
        {
            power.clear();
            findPower(i);
            int tmp=1;
            for(int j=0;j<power.size();j++)
                tmp*=(power[j]+1);
            if(tmp>mx)
                mx=tmp, id=i;
        }
        cout<<"Between "<<l<<" and "<<u<<", "<<id<<" has a maximum of "<<mx<<" divisors.\n";
    }
return 0;
}