#include <iostream>
#include <fstream>
using namespace std;

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

long long int N, P, r;
long long int divN[20];
int nrdiv, nt;


void divizori(long long N)
{
    nrdiv = 0;
    if(N % 2 == 0)
    {
        divN[++nrdiv] = 2;
        do
            N /= 2;
        while(N % 2 == 0);
    }
    for(int d = 3; 1LL * d * d <= N; d += 2)
        if(N % d == 0)
        {
            divN[++nrdiv] = d;
            do
                N /= d;
            while(N % d == 0);
        }
    if(N > 1)
        divN[++nrdiv] = N;
}

long long nrfractii(long long x)
{
    long long card = 0;
    for(int k = 1; k < nt; k++)
    {
        long long produs = 1;
        int nrbiti = 0, p2;
        for(int j = 0; (p2 = 1 << j) <= k; j++)
            if(p2 & k)
            {
                produs *= divN[j + 1];
                nrbiti++;
            }
        long long T = x / produs;
        if(nrbiti % 2 == 0) card -= T;
        else card += T;
    }
    return x - card;
}

void cautX()
{
    long long int sst = 1;
    long long int sdr = 1LL << 61;
    while(sst <= sdr)
    {
        long long int x = (sst + sdr) / 2;
        if(nrfractii(x) >= P)
        {
            r = x;
            sdr = x - 1;
        }
        else
            sst = x + 1;
    }
}

int main()
{
    f >> N >> P;
    divizori(N);
    nt = (1 << nrdiv);
    cautX();
    g << r;
    return 0;
}