#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

long long p,x,q,k,prim[11],ex[11];

long long factelem(int i){
    long long putere,suma,s;
    putere=prim[i];
    suma=0;
    s=x;
    while(s/putere>0){
        s/=putere;
        suma+=s;
    }
    return suma/ex[i];
}

long long fact(long long x){
    long long minim;
    int i;
    minim=factelem(1);
    for(i=2;i<=k;i++)
        if(factelem(i)/q<minim/q)
            minim=factelem(i);
    return minim;

}

int main(){

    freopen("gfact.in","r",stdin);
    freopen("gfact.out","w",stdout);

    long long putere,s,d,cp;

    scanf("%lld%lld",&p,&q);

    d=2;
    cp=p;
    while(d*d<=cp){
        if(cp%d==0){
            k++;
            prim[k]=d;
            while(cp%d==0){
                ex[k]++;
                cp/=d;
            }
        }
        d++;
    }
    if(cp!=1){
        k++;
        prim[k]=cp;
        ex[k]=1;
    }

    putere=1LL<<60;
    s=0;
    while(putere>0){
        x=s+putere;
        if(fact(s+putere)<=q-1)
            s+=putere;
        putere/=2;
    }

    printf("%lld",s+1);

    return 0;
}