#include <bits/stdc++.h>
using namespace std;

int p, q, NR;
int f[25], pr[25];
inline long long legendre(long long x, long long y){
    long long p = y, ans = 0;
    while(p <= x){
        ans = ans + x / p;
        p = 1LL * p * y;
    }
    return ans;
}
int main()
{
    freopen("gfact.in", "r", stdin);
    freopen("gfact.out", "w", stdout);
    scanf("%d%d", &p, &q);

    int d = 2, P = p;
    while(1LL * d * d <= P){
        if(P % d == 0){
            pr[++NR] = d;
            while(P % d == 0)
                P = P / d, ++f[NR];
        }
        ++d;
    }
    if(P > 1) pr[++NR] = P, f[NR] = 1;

    long long Sol = 0;
    for(int i = 1; i <= NR ; ++i){
        long long st = 1, dr = 2e15;
        while(st <= dr){
            long long mij = (st + dr) / 2;
            if(legendre(mij, pr[i]) < f[i] * q) st = mij + 1;
            else dr = mij - 1;
        }
        Sol = max(Sol, st);
    }
    printf("%lld", Sol);

    return 0;
}