#include<cstdio>
#include<math.h>
using namespace std;
struct Doica
{
    int x,y;
};

Doica v[15];
int legendre(int p,int n)
{
    int s=0;
    while(n)
    {
        s+=(n/p);
        n/=p;
    }
    return s;
}

int bs(int st,int dr,int poz)
{
    int med,last=-1;
    while(st<=dr)
    {
        med=st+((dr-st)>>1);
        if(legendre(v[poz].x,med)>=v[poz].y)
        {
            last=med;
            dr=med-1;
        }
        else
        st=med+1;
    }
    return last;
}

int prim(int x)
{
    if(x==0||x==1)
    return 1;
    else
    {
        if(x==2)
        return 1;
        else
        {
            if(x%2==0)
            return 0;
            else
            {
                int lim=(int)sqrt(x);
                for(int i=3;i<=lim;i=i+2)
                {
                    if(x%i==0)
                    return 0;
                }
            }
        }
    }
    return 1;
}

int main()
{
    freopen("gfact.in","r",stdin);
    freopen("gfact.out","w",stdout);
    int p,q,max=0,nr=0,nr1,x,i;
    scanf("%d%d",&p,&q);
    if(prim(p)==1)
    {
        v[1].x=p;
        v[1].y=q;
        printf("%d",bs(1,2147483647,1));
    }
    else
    {
        int lim=(int)sqrt(p);
        for(i=2;i<=lim;++i)
        {
            if(prim(i)==1&&p%i==0)
            {
                nr1=0;
                while(p%i==0)
                {
                    p/=i;
                    nr1++;
                }
                v[++nr].x=i;
                v[nr].y=nr1*q;
                if(prim(p)==1)
                {
                    v[++nr].x=p;
                    v[nr].y=q;
                }
                else
                {
                    if(p==1)
                    break;
                }
            }
        }
        for(i=1;i<=nr;++i)
        {
            x=bs(1,2147483647,i);
            if(max<x)
            max=x;
        }
        printf("%d",max);
    }
    return 0;
}