#include <bits/stdc++.h>
#define mx 1000001
#define ll long long
using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");
ll p,n,v[mx],k;


ll subm(ll a)
{
    ll sol=a, p, nrel, i,j;

    for(i=1; i<(1LL<<k); i++)
    {
        nrel=0;
        p=1;
        for(j=0; j<k; j++)
            if(i & (1LL << j))
            {
                nrel++;
                p = p*v[j+1];
            }

        if(nrel%2==1)
            sol=sol-a/p;
        else
            sol=sol+a/p;
    }

    return sol;
}

ll cbin(ll p)
{
    ll left, right, mid;
    left = 1;
    right = 1LL << 61;

    while(left <= right)
    {
        mid = (left + right) / 2;

        if (subm(mid) < p) left = mid + 1;
        else right=mid-1;
    }
    return left;
}

int main()
{
    f>>n>>p;

    ll i=2;
    while (n>1 && i*i <= n)
    {
        if(n%i== 0)
        {
            v[++k] = i;
            while(n%i == 0) n /= i;
        }
        i++;
    }
    if(n>1)
    v[++k]=n;
    g << cbin(p);

    return 0;
}