#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> per;
typedef long double LD;


const int N=200005;
const int M=1005;
const LL mod=1000000007;
const int inf=(1<<30);
const LL linf=(1LL<<61);

ifstream f("frac.in");
ofstream g("frac.out");

bool ciur[N];
LL n,fact[M],s,nr,p,rez,prime[N],l,lim,x;
LL lt,rt,md;

void Eratosthenes()
{
    ciur[1]=1;
    int H=sqrt(n);
    for(int i=2;i<=H;++i) if(!ciur[i])
    {
        prime[++s]=i;
        for(int j=2;i*j<=H;++j) ciur[i*j]=1;
    }
}

void primi(LL x)
{
    for(int i=1;i<=s && x!=1;++i) if(x%prime[i]==0)
    {
        fact[++l]=prime[i];
        while(x%prime[i]==0) x/=prime[i];
    }
    if(x!=1) fact[++l]=x;
    lim=(1<<l)-1;
}

void atr(int i,LL md)
{
    x=1LL; nr=0LL;
    for(int t=1;t<=l;++t)
    {
        if(i%2) x*=fact[t], ++nr;
        i/=2;
    }
    if(nr%2) rez+=(md/x);
    else rez-=(md/x);
}

bool check(LL md)
{
    rez=0LL;
    for(int i=1;i<=lim;++i) atr(i,md);
    return(md-rez<=p);
}

int main()
{
    f>>n>>p;
    --p;
    Eratosthenes();
    primi(n);
    lt=1LL; rt=(1LL<<61)+1;
    while(rt-lt!=1)
    {
        md=(lt+rt)/2;
        if(check(md)) lt=md;
        else rt=md;
    }
    g<<lt+1;
    return 0;
}