#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

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

#define int unsigned long long
const int INF=1e18;
vector<int>divi;

void decompose(int n)
{
    int d=2;
    while(n!=1)
    {
        int kon=0;
        while(n%d==0)
        {
            kon++;
            n/=d;
        }
        if(kon)
            divi.push_back(d);
        if(d*d>n && n!=1)
        {
            divi.push_back(n);
            n=1;
        }
        d++;
    }
}


bool valid(int x,int k)
{
    int n,mask,i,j,s=x;
    n=divi.size();
    for(mask=1;mask<(1<<n);mask++)
    {
        int kon=0;
        int p=1;
        for(i=0;i<n;i++)
        {
            if(mask & (1<<i))
            {
                kon++;
                p*=divi[i];
            }
        }
        if(kon & 1)
            s-=x/p;
        else
            s+=x/p;
    }
    return s>=k;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    int n,k;
    fin>>n>>k;
    decompose(n);
    int st=1,dr=INF,ans=0;
    while(st<=dr)
    {
        int mij=st+dr;
        mij/=2;
        if(valid(mij,k))
        {
            dr=mij-1;
            ans=mij;
        }
        else
            st=mij+1;
    }
    fout<<ans;
    fin.close();
    fout.close();
    return 0;
}