#include <iostream>
#include <fstream>

using namespace std;

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

int dp[10001], e[10001], ndp, q;

void divp(int n){
    int p, d=2;
    while(d*d<=n){
        if(n%d==0){
            dp[++ndp]=d;
            p=0;
            while(n%d==0){
                n/=d;
                p++;
            }
            e[++ndp]=p;
        }
        d++;
    }
    if(n!=1){
        dp[++ndp]=n;
        e[ndp]=1;
    }

    for(int i=1; i<=ndp; i++)
        cout<<dp[i]<<" "<<e[i]<<"\n";
}

long long putere(long long n, int p){
    long long nr=0;
    while(n>=p){
        nr+=n/p;
        n/=p;
    }
    return nr;
}

bool sedivide(long long n){
    for(int i=1; i<=ndp; i++){
        if(putere(n, dp[i])<e[i]*q){
            return false;
        }
    }
    return true;
}

int main()
{
    long long p, r=0, pas=1LL<<45;
    in>>p>>q;
    divp(p);
    while(pas!=0){
        if(!sedivide(r+pas))
            r+=pas;
        pas/=2;
    }
    r++;
    out<<r;
    return 0;
}