#include <bits/stdc++.h>
using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

long long p,n,v[1000001],k;

long long subm(long long a)
{
    long long sol=a, p, nrel, i,j;

    for(i=1; i<(1LL<<k); i++)
    {
        nrel=0;
        p=1;
        for(j=0; j<k; j++)
            if(i & (1LL << j))
            {
                nrel++;
                p = p*v[j+1];
            }

        if(nrel%2==0)
            sol=sol+a/p;
        else
            sol=sol-a/p;
    }

    return sol;
}

long long caut(long long p)
{
    long long st, dr, mij;
    st = 1;
    dr = 1LL << 61;

    while(st <= dr)
    {
        mij = (st + dr) / 2;

        if (subm(mij) < p) st = mij + 1;
        else dr=mij-1;
    }
    return st;
}

int main()
{
    f>>n>>p;

    long long i=2;
    while (n>1 && i*i <= n)
    {
        if(n%i== 0)
        {
            v[++k] = i;
            while(n%i == 0) n /= i;
        }
        i++;
    }
    if(n>1)
    v[++k]=n;
    g << caut(p);
    return 0;
}