#include <bits/stdc++.h>
#define NMAX 100005
#define MOD 666013
#define INF 0x3f3f3f3f
#define x first
#define y second

using namespace std;

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

vector<long long> diviz;

long long intr(long long x) {
	long long i,j,prod,sol=x,lim=(1<<diviz.size());

	for(i=1;i<lim;++i) {
		prod=1;
		for(j=0;j<diviz.size();++j) {
			if(i&(1<<j))
				prod*=-diviz[j];
		}

		sol+=x/prod;
	}
	return sol;
}

int main() {
	long long st,dr,mid,n,p,d,i;
	long double smaller;

	fin>>n>>p;

	d=2;
	while(d*d<=n) {
		if(n%d==0) {
			diviz.push_back(d);

			while(n%d==0)
				n/=d;
		}

		++d;
	}
	if(n!=1) diviz.push_back(n);

	st=1;
	dr=(1LL<<61);
	while(st<=dr) {
		mid=(st+dr)/2;

		if(intr(mid)<p) st=mid+1;
		else dr=mid-1;
	}

	fout<<st;

	return 0;
}