#include <fstream>
#include <vector>
using namespace std;

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

#define int long long

int n,p,vf[11];
vector<vector<int> >v(11);
vector<int>fp;

void rec(int x)
{
    if (x==fp.size())
    {
        int cnt=0,prod=1;
        for (int i=0; i<fp.size(); i++)
        {
            if (vf[i]) {cnt++; prod*=fp[i];}
        }
        v[cnt].push_back(prod);
        return;
    }
    vf[x]=1;
    rec(x+1);
    vf[x]=0;
    rec(x+1);
}

int verif(int x)
{
    int cnt=0;
    for (int i=1; i<=10; i++)
    {
        for (int j=0; j<v[i].size(); j++)
        {
            if (i%2==1) cnt+=x/v[i][j];
            else cnt-=x/v[i][j];
        }
    }
    return cnt;
}

bool prm(int a,int b)
{
    if (a<b) swap(a,b);
    while (b)
    {
        swap(a,b);
        b%=a;
    }
    if (a>1) return 0;
    return 1;
}

int32_t main()
{
    cin>>n>>p;
    int nn=n;
    for (int i=2; i*i<=n; i++)
    {
        if (n%i==0) fp.push_back(i);
        while (n%i==0) n/=i;
    }
    if (n>1) fp.push_back(n);
    rec(0);
    int s=1,r=1e18;
    while (s<r)
    {
        int mid=(s+r+1)/2,nr=verif(mid);
        if (mid-nr>=p) r=mid-1;
        else s=mid;
    }
    while (1)
    {
        s++;
        if (prm(s,nn)) {cout<<s; break;}
    }
}