#include <bits/stdc++.h>

using namespace std;

map<int, int> m;

int nr(int n, int p)
{
    if(!n) return 0;
    int k = 0;
    while(!(n % p)) n /= p, k++;
    return k;
}

int l(int n, int p)
{
    int k = 0, cnt = 0;
    while(cnt < p)
    {
        cnt += nr(k, n);
        k += n;
    }
    return k - n;
}

int main()
{
    freopen("gfact.in", "r", stdin);
    freopen("gfact.out", "w", stdout);
    int p, q, k = 2;
    scanf("%d%d", &p, &q);
    while(p > 1 and k * k <= p)
    {
        while(!(p % k)) m[k] += q, p /= k;
            k++;
    }
    m[p] = q;
    k = -1;
    for(map<int, int>::iterator it = m.begin(); it != m.end(); it++)
        k = max(k, l(it -> first, it -> second));
    printf("%d", k);
    return 0;
}