# include <bits/stdc++.h>
using namespace std;
ifstream fi("gfact.in");
ofstream fo("gfact.out");
# define db double
# define ll long long
# define pi 3.14159265359
# define x first
# define y second
# define pb push_back
# define rad(x) (x * pi / 180)
const int p_1[] = {1,-1};
const int mod1 = 1e9 + 7;
const int mod2 = 666013;
const int mod3 = 997;
template < class T > inline T sqr(T x) {return x*x;};
template < class T > inline T min(T a,T b,T c) {return min(a,min(b,c));};
template < class T > inline T min(T a,T b,T c,T d) {return min(min(a,b),min(b,c));};
template < class T > inline T max(T a,T b,T c) {return max(a,max(b,c));};
template < class T > inline T max(T a,T b,T c,T d) {return max(max(a,b),max(b,c));};
template < class T > inline T det(T a,T b,T c,T d) {return a * c - b * d;};
template < class T > inline T det(T s[3][3])
{
    return - s[0][0] * det(s[1][1],s[1][2],s[2][1],s[2][2]) + s[0][1] * det(s[1][0],s[1][2],s[2][0],s[2][2]) - s[0][2] * det(s[1][0],s[1][1],s[2][0],s[2][1]);
}
template < class T1 , class T2 , class T3 > inline T3 pow(T1 a,T2 b,T3 mod) {T3 ans = 1;while (b){if (b&1) ans = (1LL * ans * a) % mod;a = (1LL * a * a) % mod;b >>= 1;}return ans;}
template < class T > T phi(T n){T cnt = n,p = n,ans = n;for (T i = 2;i*i <= p;++i)if (!(cnt%i)){ans /= i;ans *= (i-1);while (!(cnt%i)) cnt /= i;}if (cnt > 1) ans /= cnt,ans *= (cnt - 1);return ans;}
template < class T > T f(T n,T k)
{
    return n < k ? 0 : n / k + f(n / k,k);
}
vector < pair < int , int > > s;
int main(void)
{
    int p,q;
    fi>>p>>q;
    for (int i = 2;i*i <= p;++i)
        if (!(p%i))
        {
            int cnt = 0;
            while (!(p%i)) p /= i,++cnt;
            s.pb({i,cnt * q});
        }
    if (p != 1) s.pb({p,q});
    p = 1;
    ll u = 1ll << 52;
    ll bst = u;
    while (p <= u)
    {
        ll m = (p + u) / 2;
        ll mn = 1ll << 62;
        for (auto it : s) mn = min(mn,f(m,1ll * it.x) / it.y);
        if (mn) bst = m,u = m - 1;else p = m + 1;
    }
    return fo << bst << '\n',0;
}