#include <bits/stdc++.h>

using namespace std;

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

long long gfact(long long fact, long long base)
{
    long long ret = 0;
    while(fact)
    {
        fact /= base;
        ret += fact;
    }
    return ret;
}

long long cbin(long long p, long long q)
{
    long long index = 0;
    for(long long step = (1LL<<60); step > 0; step >>= 1)
    {
        //cout << step << endl;
        //cout << index+step << " " << p << " " << gfact(index+step, p) << endl;

        if(q > gfact(index+step, p)) index += step;
    }

    return index+1;
}

int main()
{
    long long p, q; in >> p >> q;

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

    long long big = 1, exp = 1;
    for(int i = 2; i*i <= p; i++)
    {
        if(p%i == 0)
        {
            big = i;
            exp = 0;

            while(p%i == 0)
            {
                p /= i;
                exp++;
            }
        }
    }
    if(p > 1) { big = p; exp = 1; }

    //out << gfact(4, 2) << endl;

    //out << big << " " << exp << " " << q << endl;

    out << cbin(big, 1LL*q*exp);
}