#include <bits/stdc++.h>
using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");
long long p,n,v[1000001],m,d=2;
bool pinex(long long a)
{
    long long x,nr,pr,sol=0,i,j;
    x=1<<m;
    for(i=1;i<x;i++)
    {
        nr=0;
        pr=1;
        for(j=0;j<m;j++)
        {
            if((i&(1<<j))!=0)
            {
                nr++;
                pr=pr*v[j+1];
            }
        }
        if(nr%2==1)sol+=a/pr;
        else sol-=a/pr;
    }
    if(a-sol<p)return 1;
    return 0;
}
long long cb(long long p)
{
    long long st,dr,mid;
    st=1;
    dr=LONG_MAX;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(pinex(mid))st=mid+1;
        else dr=mid-1;
    }
    return st;
}
int main()
{
    fin>>n>>p;
    while(d<=sqrt(n))
    {
        if(n%d==0)v[++m]=d;
        while(n%d==0)n=n/d;
        d++;
        if(n<=1)break;
    }
    if(n>1)v[++m]=n;
    fout<<cb(p);
    return 0;
}