#include<stdio.h>

#define lint long long

int ind, q[25], sol[25], nrs;
lint n, p, i, x, rez, pr;

void back(int k){
	if (k == ind+1){
		pr = 1; nrs = 0;
		for (int i = 1; i <= ind; i ++)
			if (sol[i])
				pr *= q[i], nrs ++;

		if (nrs > 0)
			if (nrs % 2 == 0)
				rez -= x / pr;
			else
				rez += x / pr;

		return ;
	}

	sol[k] = -1;
	while (sol[k] < 1){
		sol[k] ++;
		back(k+1);
	}
}
lint bs(){
	lint li = 1, ls = (lint)1 << 61, gs = -1;

	while (li <= ls){
		x = (li + ls) / 2;

		rez = 0;
		for (int i = 1; i <= ind; i ++) sol[i] = 0;
		back(1);

//		printf("pentru %lld  %lld\n", x, rez);

		if (x - rez >= p){
			gs = x;
			ls = x-1;
		}
		else
			li = x+1;
	}

	return gs;
}

int main()
{
	freopen("frac.in", "rt", stdin);
	freopen("frac.out", "wt", stdout);

	scanf("%lld%lld", &n, &p);

	for (i = 2; i*i <= n; i ++)
		if (n % i == 0){
			q[++ind] = i;

			for (; n % i == 0; n /= i);
		}
	if (n != 1)
		q[++ind] = n;

//	for (i = 1; i <= ind; i ++)
//		printf("%d\n", q[i]);

	printf("%lld\n", bs());
	
	return 0;
}