#include<stdio.h>
#include<math.h>
#include<algorithm>

using namespace std;

long long p;

long long nrzero(long long val,long long val2)
{
	long long rez=0;
	do
	{
		val/=val2;
		rez+=val;
	} while (val/val2!=0);
	return rez;
}

long long  cb(long val3)
{
	long long st=1,dr,val,med;
	dr=(long long )1<<62;
	while (st<=dr)
	{
		med=dr-(dr-st)/2;
		val=nrzero(med,val3);
		if (val>=p)
			dr=med-1;
		else
			st=med+1;
	}
	val=nrzero(med,val3);
	if (val<p)
	{
		med++;
		val=nrzero(med,val3);
	}
	if (val>=p)
		return med;
	else
		return -1;
}

int main()
{

    long long n=0,n2,nr,i,max2=0;

    freopen("gfact.in","r",stdin);
    freopen("gfact.out","w",stdout);

    scanf("%lld %lld",&n,&p);

    n2=n;

    if (n%2==0)
    {
        nr=0;
        while (n%2==0)
            n/=2,nr++;
        p*=nr;
        max2=max(max2,cb(2));
        p/=nr;
    }
    for (i=3;i<=n2/2;i+=2)
        if (n%i==0)
        {
            nr=0;
            while (n%i==0)
                n/=i,nr++;
            p*=nr;
            max2=max(max2,cb(i));
            p/=nr;
        }

    printf("%lld",max2);

    return 0;

}