#include <fstream>

using namespace std;

ifstream in("gfact.in");
ofstream out("gfact.out");

int v[9], e[9], np, q;

long long multipl(long long n, int prim)
{
    long long sum;

    sum = 0;
    while(n)
    {
        sum += n / v[prim];
        n /= v[prim];
    }

    return sum;
}

bool verifica(long long n)
{
    int i;

    for(i = 0; i < np; i++)
        if(multipl(n, i) < (long long)q * e[i])
            return 0;

    return 1;
}

int main()
{
    int p, prim, exp;
    long long i, pas;

    in>>p>>q;

    if(p == 1)
    {
        out<<0<<'\n';
        return 0;
    }

    prim = 2;
    np = 0;
    if(p % prim == 0)
    {
        v[np] = prim;
        exp = 0;
        while(p % prim == 0)
        {
            p /= prim;
            exp++;
        }
        e[np] = exp;
        np++;
    }

    prim = 3;
    while(prim * prim <= p)
    {
        if(p % prim == 0)
        {
            v[np] = prim;
            exp = 0;
            while(p % prim == 0)
            {
                p /= prim;
                exp++;
            }
            e[np] = exp;
            np++;
        }
        prim += 2;
    }

    if(p != 1)
    {
        v[np] = p;
        e[np] = 1;
        np++;
    }

    i = 0;
    pas = 1LL << 45;

    while(pas)
    {
        if(!verifica(i + pas))
            i += pas;
        pas /= 2;
    }
    out<<i + 1<<'\n';
    return 0;
}