#include <fstream>
#include <vector>
#define int long long
using namespace std;
ifstream cin("frac.in");
ofstream cout("frac.out");
using pii = pair<int,int>;
int n , p;
vector <int> pf;
signed main()
{
    cin >> n >> p;
    for(int i = 2 ; i * i <= n ; ++i)
    {
        if(n%i == 0) pf.push_back(i);
        while(n%i == 0) n/=i;
    }
    if(n > 1) pf.push_back(n);
    int st = 1 , dr = 1e18 , ans = -1;
    while(st <= dr)
    {
        int mij = st + (dr-st)/2;
        int cnt = 0;
        for(int i = 0 ; i < (1<<pf.size()) ; ++i)
        {
            int hm = 0;
            int prod = 1;
            for(int j = 0 ; j < (int)pf.size() ; ++j)
            {
                if(i & (1<<j))
                {
                    prod *= pf[j];
                    hm++;
                }
            }
            if(hm&1)
            {
                cnt -= mij/prod;
            }
            else cnt += mij/prod;
        }
        if(cnt >= p)
        {
            ans = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    cout << ans;
    return 0;
}