#include<fstream>
#include<iostream>
#include<math.h>
using namespace std;
struct factori
    {
        int x,y;
    };
int numar (factori t)
{
    int i=1,c=0;
    while(c<t.y)
    {   i++;
        int j=i;
        while (j%t.x==0) {c++;j/=t.x;}
    }
    return i;
}
int main()
{
    factori z[20];
    long p,q,a,b,c;
    ifstream f("gfac.in");
    ofstream g("gfac.out");
    f>>p>>q;
    a=pow(p,q);
    c=a;
    int j=0;
    for(int i=2;(i<=c)&&(a!=1);i++)
        if (a%i==0)
        {
          z[++j].x=i;z[j].y=0;
        while (a%i==0)
        {
            z[j].y++;a/=i;
        }
        }
        int maxi=0;
    for (int i=1;i<=j;i++) {c=numar(z[i]);if (c>maxi) maxi=c;};
    g<<maxi;
    f.close();
    g.close();
    return 0;
}