Uva 11353 - A Different Kind of Sorting

/*
    Verdict: Accepted
    Time: 0.280

*/

#include<bits/stdc++.h>

#define limit 2000001
#define sf scanf
#define pf printf
using namespace std;

typedef long long LL;

struct my
{
    LL index, divisor;
};

my factors[limit];

typedef bitset<limit>bsarry;

bool cmp(my a, my b)
{
    if(a.divisor < b.divisor)
    {
        return true;
    }

    else if(a.divisor == b.divisor)
    {
        return a.index < b.index;
    }

    else
    {
        return false;
    }
}

void fun_factors()
{
    bsarry bs;

    LL i,j;

    bs.set();
    bs[0] = bs[1] = 0;

    factors[1].index = 1;
    factors[1].divisor = 1;

    for(i=2; i<limit; i++)
    {
        if(bs[i])
        {
            factors[i].index=i;
            factors[i].divisor = 1;

            for(j=i*2; j<limit; j+=i)
            {
                factors[j].index = j;
                factors[j].divisor = 1 + factors[j / i].divisor;

                bs[j] = 0;
            }
        }
    }

    sort(factors, factors+limit, cmp);

    //for(i=1987781;i<=2000000;i++)cout << factors[i].index << " " << factors[i].divisor << "\n";
}

int main()
{
    fun_factors();
    int tc=0;
    LL n;
    while(~sf("%lld",&n) and n)
    {
        pf("Case %d: %lld\n", ++tc, factors[n].index);
    }

    return 0;
}