#include <fstream>
#include <math.h>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
int n, care, i, j, t, d;
long long p, u, m, v[20], aux, c, h;

long long afla(long long a){
    int i, j, k, nr, x[20];
    long long u, p, s, aux;
    u=n;
    s=0;
    j=1;
    for(j=0; j<=t; j++)
        x[j]=0;
    while(x[0]!=1)
    {
        j=t;
        while(x[j]==1)
        {
            x[j]=0;
            j--;
        }
        x[j]=1;
        if(x[0]==1)
            break;
        p=1;
        nr=0;
        for(j=1; j<=t; j++)
            if(x[j]==1)
            {
                nr++;
                p*=v[j];
            }
        if(nr%2==0)
            s-=a/p;
        else
            s+=a/p;
    }
    return a-s;
}

int main(){
	f>>n>>care;
	f.close();
	c=n;
	d=2;
	int rn=(int)sqrt(n*1.0);
	while(c!=1 && d<=rn)
	{
		if(c%d==0)
		{
			v[++t]=d;
			while(c%d==0)
				c/=d;
		}
		d++;
	}
	if(c!=1)
		v[++t]=c;
	p=1;
	u=(1LL<<62);
	while(p<=u)
	{
		m=(p+u)/2;
		h=afla(m);
        if(h<care)
            p=m+1;
        else
            u=m-1;

	}
	g<<p<<"\n";
	g.close();
	return 0;
}