#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;

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

	fin>>n>>p;
	aux=n;

	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);

	/*for(i=1;i<=15;++i) {
		smaller =i;
		for(auto it:diviz) {
			//if(smaller<it) continue;
			//if(smaller%it!=0) smaller+=it;

			smaller*=1.0*(it-1)/it;
			//smaller*=(it-1);
		}

		fout<<smaller<<' ';
	}*/

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

		smaller=mid;
		for(auto it:diviz)
			smaller*=1.0*(it-1)/it;


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

	fout<<st;

	return 0;
}