#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++;
	
    }
	
    if(p > 1) 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;
	
}