#include <fstream>
#include <vector>

using namespace std;
ifstream cin("frac.in");
ofstream cout("frac.out");

vector<long long>primi;
long long n,poz;
long long c=61;

long long pinex(long long a)
{
    long long k=primi.size();
    long long rsp=0;
    for(long long mask = 1;mask<((long long)1<<k);mask++)
    {
        long long nr=0,p=1;
        for(long long j=0;j<k;j++)
            if(mask&((long long)1<<j))
                nr++,p*=primi[j];
        if(nr%2==0)
            rsp-=a/p;
        else
            rsp+=a/p;
    }
    return a-rsp;
}

void fact(long long nr)
{
    long long d=2;
    while(nr>1)
    {
        bool intrat=0;
        while(nr%d==0)
            nr/=d,intrat=1;

        if(intrat)
            primi.push_back(d);
        d++;
        if(d*d>nr)
            d=nr;
    }
}

int32_t main()
{
    cin>>n>>poz;
    fact(n);

    long long st=0,dr=((long long)1<<c)+1;
    while(st+1<dr)
    {
        long long mid=((st+dr)>>(long long)1);
        if(pinex(mid)<poz)
            st=mid;
        else
            dr=mid;
    }
    cout<<dr;
    return 0;
}