#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
#define MOD 1000000007

ifstream fin("frac.in");
ofstream fout("frac.out");

int dist(int x1,int y1,int x2,int y2)
{
    return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}
int det(int x1,int y1,int x2,int y2,int x3,int y3)
{
    return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
}


ll gcd(ll a,ll b)
{
    while(b)
    {
        ll r = a%b;
        a=b;
        b=r;
    }
    return a;
}
long long k;
vector<long long> f;

ll cnt(ll n)
{
    ll k=0;
    for(int i=1;i<(1<<f.size());i++)
    {
        ll p=1,x=0;
        for(int j=0;j<f.size();j++)
        {
            if((i >> j)&1)p*=f[j],++x;
        }
        if(x%2)k+= n/p;
        else k-= n/p;
    }
    return k;
}
int main()
{
    ll n,t;
    fin >> n >> k;
    t=n;
    ll d=2;
    while(n>1)
    {
        if(n%d==0)
        {
            while(n%d==0)n/=d;
            f.push_back(d);
        }
        d++;
    }
    n=t;
    ll l=1,r=LLONG_MAX-10;
    while(l<=r)
    {
        ll m = (l+r)/2;
        ll x=cnt(m);
        if(m-x==k && gcd(m,n)==1)
        {
            fout << m;
            break;
        }
        if(m-x >= k)r=m-1;
        else l=m+1;
    }


    // a= i + b/2 - 1  i= a+1-b/2
}