Amit And Prime Numbers - HackerEarth

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    int prime[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
    long long int high=1000000000000000000;
    while(t--)
    {
        long long int k;
        cin >> k;
        long long int lower=1;
        long long int upper=1000000000000000000;
        long long int ans;
        while(lower<upper)
        {
            ans=(lower+upper)/2;
            long long int total=0;
            for(int i=1;i<(1<<15);i++)
            {
                long long int c=0;
                long long int mul=1;
                for(int j=0;j<15;j++)
                {
                    if (i&(1<<j)) {
                        mul=mul*prime[j];  
                        if (mul>high)
                        {
                            mul=-1LL;
                            break;
                        }
                        c++;
                    }
                }
               // cout << mul << " ";
                if(mul!=-1)
                {
                long long int temp=ans/mul;
                if(c%2)
                {
                    total=total+temp;
                }
                else
                {
                    total=total-temp;
                }
                }
            }
           // cout << total << " " << ans  << endl;
            if(total<k)
            {
                lower=ans+1;
            }
            else
            {
                upper=ans;
            }
            
        }
        cout << lower << endl;
    }
}