#include <stdio.h>
#include <iostream>

using namespace std;

typedef long long ll;
ll n, p, f[11];
short nrF;
/// sunt maxim 10 factori primi;
void fact() {
    if(n % 2 == 0) {
        f[++nrF] = 2;
        while(n%2 == 0) n /= 2;
    }
    for(int i = 3; i*i <= n; i += 2) {
        if(n%i == 0) {
            f[++nrF] = i;
            while(n%i == 0) n /= i;
        }
    }
    if(n > 1) f[++nrF] = n;
}

ll elem(ll x) {
    ll s = x;
    for(int i = 1; i < (1<<nrF); i++) {
        short nr = 0;
        ll p = 1;
        for(int j = 0; j < nrF; j++)
            if((1<<j) & i) {
                p *= f[j+1];
                nr++;
            }
        if(nr%2 == 0)
            s += x/p;
        else s -= x/p;
    }
    return s;
}

ll cauta() {
    ll st = 0, dr = 1LL << 61, poz = 0;
    while(st <= dr) {
        ll mij = st + (dr-st)/2;
        if(elem(mij) >= p)
            dr = mij-1, poz = mij;
        else st = mij+1;
    }
    return poz;
}

int main()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    scanf("%lld %lld", &n, &p);
    fact();
    printf("%lld", cauta());
    return 0;
}