Uva 294 Solution

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
vector<int>p;

void rob(long long int m)
{
    long long int l, i, j;

    l = sqrt(m);
    int a[l+1];

    for(i=1; i<=l; i++)
    {
        a[i] = 0;
    }

    a[1] = 1;
    p.push_back(2);

    for(i=4; i<=l; i+=2)
        a[i] = 1;

    for(i=3; i<=l; i+=2)
    {
        if(a[i] != 1)
        {
            p.push_back(i);
            for(j=i*i; j<=l; j+=i*2)
            {
                a[j] = 1;
            }
        }
    }

}


long long int anik(long long int n)
{
    long long int d, c, i;
    d = 1;
    for(i=0; i<p.size(); i++)
    {
        if(n%p[i] == 0)
        {
            c = 1;
            while(n%p[i] == 0)
            {
                n = n/p[i];
                c++;
            }
            d = d*c;
            if(n == 1)
                break;
        }
    }
    if(n == 1 && d == 1)
        return 1;
    else if(n != 1 || d == 1)
        return 2;
    else
        return d;
}
int main()
{
    long long int x, y, i, j, t, r, maxi, e, o;

    while(cin >> o)
    {
        for(j=1; j<=o; j++)
        {
            cin >> x >> y;
            maxi = -1;
            rob(y);
            for(i=x; i<=y; i++)
            {
                t = anik(i);
                if(t>maxi)
                {
                    maxi = t;
                    e = i;
                }
            }

            cout << "Between " << x << " and " << y << ", " << e << " has a maximum of " << maxi << " divisors." << endl;
            p.clear();
        }
    }
    return 0;
}

Comments