#include <iostream>
#include <fstream>

using namespace std;

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

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

int main()
{
    int i,q,m;
    long int p;
    long long int n=0,pas;
    fin>>p>>q;
    for(i=1;i<=(p/2)+1;i++){
        if(p%i==0){
            p=p/i;
            m=i;
        }
    }
    p=m;
    pas=1073741824;
    while(pas!=0){
        if(qc(n+pas,p)<q){
            n+=pas;
        }
        pas/=2;
    }
    fout<<n+1;
    return 0;
}