294 - Divisors

#include<stdio.h>
#include<vector>
#include<math.h>
#define MAX 40009
using namespace std;
bool arr[MAX];
vector<long long int>prime;
void sieve()
{
    long long int i,j,k;
    k=sqrt(MAX);
    for(i=3; i<=k; i+=2)
    {
        if(arr[i]==0)
        {
            for(j=i*i; j<MAX; j+=i+i)
            {
                arr[j]=1;
            }
        }
    }
    arr[1]=1;
    arr[0]=1;
    for(i=4; i<MAX; i=i+2)
    {
        arr[i]=1;
    }
    prime.push_back(2);
    for(i=3; i<MAX; i=i+2)
    {
        if(arr[i]==0)
        {
            prime.push_back(i);
        }
    }
}
int main()
{
    long long int test_case,L,U,i,j,k,l,cnt,counter,koyta_divisor,divisor;
    sieve();
    scanf("%lld",&test_case);
    while(test_case--)
    {
        scanf("%lld%lld",&L,&U);
        koyta_divisor=0;
        k=prime.size();
        for(l=L;l<=U;l++)
        {
            counter=1;
            int i=l;
            for(j=0;j<k&&i!=1;j++)
            {
                if(i%prime[j]==0)
                {
                    cnt=0;
                    while(i%prime[j]==0)
                    {
                        cnt++;
                        i=i/prime[j];
                    }
                    counter*=(cnt+1);
                }
            }
            if(koyta_divisor<counter)
            {
                koyta_divisor=counter;
                divisor=l;
            }
        }
        printf("Between %lld and %lld, %lld has a maximum of %lld divisors.\n",L,U,divisor,koyta_divisor);
    }

    return 0;
}