#include <iostream>
#include <fstream>
#include <vector>


using namespace std;

ifstream in("gfact.in");
ofstream out("gfact.out");


long long int p,q;

void cit(){
    in>>p>>q;
}
void afis(vector<pair<long long int,long long int> >perechi){
    for(pair<long long int,long long int> it : perechi)
        cerr<<it.first<<"^"<<it.second<<"\n";
}
void diviz(long long int p,vector<pair<long long int,long long int> >&perechi){
    long long int d = 2,cnt;
    while(d*d <= p){
        cnt = 0;
        if(p % d == 0){
            while(p % d == 0){
                p /= d;
                cnt++;
            }
            perechi.push_back(make_pair(d,cnt));
        }
        d++;
    }
    if(p != 1)
        perechi.push_back(make_pair(p,1));
}
bool validare(long long int x,vector<pair<long long int,long long int> > perechi_p){

    bool ok = false;

    for(pair<long long int,long long int>it : perechi_p){
        unsigned long long int a = it.first;
        int p = it.second;
        unsigned long long int cnt = 0;

        while(x >= a){
            cnt += x / a;
            a *= it.first;
        }
        if(p <= cnt)
            ok = true;
    }
    return ok;
}
void cautbin(){
    long long int pas = 1LL<<50,r = 0;

    vector<pair<long long int,long long int> >perechi_p;
    diviz(p,perechi_p);


    while(pas){
        if(validare(r+pas,perechi_p) == false)
            r += pas;
        pas /= 2;
    }
    r ++;
    out<<r;
}

int main()
{
    cit();
    cautbin();

    return 0;
}