#include <bits/stdc++.h>
#define VMAX 45000
#define NMAX 60000000000000
using namespace std;

bitset<VMAX/2> ciur; //ciurul lui eratostene
vector<int> nr_prime; //numerele prime

void eratostene() //ciurul lui eratostene
{
    for(int i=3; i*i<=VMAX; i+=2)
    {
        if(ciur[i/2]==0)
        {
            for(int j=i*i; j<=VMAX; j+=2*i)
                ciur[j/2]=1;
        }
    }
    nr_prime.push_back(2);
    for(int i=3; i<=VMAX; i+=2)
    {
        if(ciur[i/2]==0)
            nr_prime.push_back(i);
    }
}

pair<long long, int> prim_maxim(long long nr)
{
    pair<long long, int> prim_maxim={0, 0};
    for(int i=0; i<nr_prime.size(); i++)
    {
        if(nr%nr_prime[i]==0)
        {
            prim_maxim.first=nr_prime[i];
            prim_maxim.second=0;
            while(nr%nr_prime[i]==0)
            {
                prim_maxim.second++;
                nr/=nr_prime[i];
            }
        }
    }
    if(nr>1)
    {
        prim_maxim.first=nr;
        prim_maxim.second=1;
    }
    return prim_maxim;
}

long long div_fact(long long p, long long fact) //numarul de puteri a lui p din factorialul lui fact
{
    long long div_fact=0;
    long long putere=p;
    while(putere<=fact)
    {
        div_fact+=fact/putere;
        putere*=p;
    }
    return div_fact;
}

long long cautare_binara(long long p, long long q)
{
    long long st=0, dr=NMAX, b=0;
    while(st<=dr)
    {
        long long mij=st+(dr-st)/2;
        if(div_fact(p, mij)>=q)
        {
            b=mij;
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    return b;
}

int main()
{
    ifstream cin("gfact.in");
    ofstream cout("gfact.out");
    eratostene();
    long long p, q;
    cin >> p >> q;
    long long prim=1; //cel mai mare nr prim care il divide pe p
    long long putere=1; //puterea la care apare acel nr prim

    pair<long long, int> prim_max=prim_maxim(p);

    prim=prim_max.first;
    putere=prim_max.second;

    putere*=q;
    cout << cautare_binara(prim, putere);

    return 0;
}