#include <stdio.h>

const int NR_DIV = 110010;

long long N, P;
int e[NR_DIV];
long long div[NR_DIV];

void eratost()
{
	for (int i = 2; i <= NR_DIV - 10; i ++) {
		if (!e[i]) {
			if (N % i == 0) div[++ div[0]] = i;
			for (int j = i * 2; j <= NR_DIV - 10; j += i) e[j] = 1;
		}
	}
}

long long cate(long long x)
{
	int biti;
	long long s, rez = 0;

	for (long long c = 1; c < (1LL << div[0]); c ++) {

		biti = 0;
		s = 1;
		for (int i = 0; i < div[0]; i ++) {
			if (c & (1 << i)) {
				s *= div[i + 1];
				biti ++;
			}
		}

		if (biti % 2 == 1) rez += (x / s);
		else rez -= (x / s);
	}

	return (x - rez);
}

long long BS()
{
	long long i, step, MAX = 1LL << 62;

	for (step = 1; step < MAX; step <<= 1);
	for (i = 0; step; step >>= 1) {
		if (i + step <= MAX && cate(i + step) < P) i += step;
	}

	return i + 1;
}

int main()
{
	freopen("frac.in", "r", stdin);
#ifndef _SCREEN_
	freopen("frac.out", "w", stdout);
#endif

	scanf("%lld %lld\n", &N, &P);

	eratost();

	printf("%lld\n", BS());

	return 0;
}