#include <bits/stdc++.h>
#define FILES freopen("frac.in" , "r" , stdin) , freopen("frac.out" , "w" , stdout)
#define ull unsigned long long
#define ll long long

using namespace std;

ll n , p;

ll a[20];

void decomp(ll x)
{
    for(ll d = 2 ; d * d <= x ; d++)
    {
        ll e = 0;

        while(x % d == 0)
            ++e , x /= d;

        if(e)
            a[++a[0]] = d;
    }

    if(x > 1)
        a[++a[0]] = x;
}

ll ans = 0;

void bkt(ll k , ll cnt , ll prod , ll A)
{
    if(k > a[0])
    {
        if(cnt == 0)
            return;

        ans += A / prod * (cnt % 2 ? 1 : -1);
    }
    else
    {
        bkt(k + 1 , cnt , prod , A);
        bkt(k + 1 , cnt + 1 , prod * a[k] , A);
    }
}

signed main()
{
    FILES;

    cin >> n >> p;
    decomp(n);

    ll l = 1 , r = LLONG_MAX , mid = 0 , P = 0;

    while(l <= r)
    {
        mid = (l + r) / 2;
        ans = 0;
        bkt(1 , 0 , 1 , mid);

        if(mid - ans >= p)
            P = mid , r = mid - 1;
        else l = mid + 1;
    }

    cout << P;

    return 0;
}