Class - 29 : Task - 2

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mx=1e6+123;
bitset<mx> isprime;
vector<ll>primes;
vector<pair<ll,ll>>vp;
bool compare(const pair<ll, ll>& a, const pair<ll, ll>& b) {
    if (a.first==b.first) {
        return a.second>b.second;
    }
    if (a.first<b.first) {
        return true;
    }
    return false;
}
void prime_gen(ll n)
{
    isprime[2]=1;
    for(ll i=3;i<=n;i+=2) isprime[i]=1;
    for(ll i=3;i*i<=n;i+=2)
    {
        if(isprime[i]==1)
        {
            for(ll j=i*i;j<=n;j+=2*i)
            {
                isprime[j]=0;
            }
        }
    }
    primes.push_back(2);
    for(ll i=3;i<=n;i+=2)
    {
        if(isprime[i]==1) primes.push_back(i);
    }
}
void prime_div(ll i)
{
    ll p=i;
    ll ans=1;
    for(auto prime:primes)
    {
        if(prime*prime>i) break;

        if(i%prime==0)
        {
             ll cnt=0;
            while(i%prime==0)
            {
                cnt++;
                i/=prime;
            }
             ans*=(cnt+1);
        }

    }
    if(i>1) ans*=2;
    vp.push_back({ans,p});
}
int main()
{
    prime_gen(1e6);
    for(int i=1;i<=1000;i++)
    {
         prime_div(i);
    }
    sort(vp.begin(),vp.end(),compare);
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        int n;
        cin>>n;
        cout<<"Case "<<i<<": "<<vp[n-1].second<<endl;
    }

}