#include <cstdio>
using namespace std;

const int NMAX = 10010;

long long N, P, K, Div[NMAX];

bool Check(long long MaxNum)
{
    long long Ans = 0;
    for(int Conf = 0; Conf < (1 << K); ++ Conf)
    {
        long long Prod = 1;
        for(int i = 0; i < K; ++ i)
            if(Conf & (1 << i))
                Prod *= -Div[i];
        Ans += MaxNum / Prod;
    }
    return P <= Ans;
}

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

    scanf("%lld %lld", &N, &P);
    for(long long i = 2; i * i <= N; ++ i)
        if(N % i == 0)
        {
            while(N % i == 0) N /= i;
            Div[ K++ ] = i;
        }
    if(N > 1) Div[ K++ ] = N;

    long long Ans = 0;
    for(long long Step = 61; Step >= 0; Step --)
        if(Check(Ans + Step) == 0)
            Ans += Step;

    printf("%lld\n", Ans + 1);
}