#include <cstdio>

using namespace std;

FILE *f, *g;

typedef long long lint;

lint n, p;

lint rez;

lint divs[1001];

lint combs[10009];

int c;

int k;

void readFile()
{
    f = fopen("frac.in", "r");

    fscanf(f, "%lld%lld", &n, &p);

    fclose(f);
}

lint ith(lint nr)
{
    int i;

    lint poz = 0;

    for(i = 1; i <= c; i ++)
        poz += nr / combs[i];

    ///Poz - neprime
    //printf("%lld %lld %lld\n", nr, poz, nr - poz);

    return (nr - poz);
}

lint cautBin()
{
    lint i = 0;
    lint pas = 1LL << 61;

    while(pas != 0)
    {
        if(ith(i + pas) < p)
            i += pas;

        pas /= 2;
    }

  //   printf("++%lld %lld\n", i, ith(11));

    return i + 1;
}

void desc(lint n)
{
    lint c = n;

    lint d = 2;
    lint p = 0;

    while(c % d == 0)
        p ++, c /= 2;

    if(p > 0)
        divs[++ k] = d;

    d ++;

    while(d * d <= c)
    {
        p = 0;

        while(c % d == 0)
        {
            c /= d;

            p ++;
        }

        if(p > 0)
            divs[++ k] = d;

        d += 2;
    }

    if(c > 1)
        divs[++ k] = c;
}

void getCombs()
{
    int i = 0;
    int j;

    lint prod;
    lint nrs;

    for(i = 1; i < (1 << k); i ++)
    {
        prod = 1;
        nrs = 0;

        for(j = 0; j < k; j ++)
        {
            if(((1 << j) & i) != 0)
                prod *= divs[j + 1], nrs ++;
        }


        if(nrs % 2 == 1)
            nrs = 1;

        else
            nrs = -1;

        combs[++ c] = prod * nrs;

        //printf("%lld\n", prod);
    }
}

void solve()
{
    desc(n);

    getCombs();

    rez = cautBin();
}

void printFile()
{
    g = fopen("frac.out", "w");

    fprintf(g, "%lld\n", rez);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}