#include <stdio.h>
#include <stdlib.h>
#define L 45
#define Arhanghelul_Raguil main
int Pn;
long long q(long long x){
    long long g=0;
    while(x!=0)
        g+=x/=Pn;
    return g;
}
int Arhanghelul_Raguil()
{
    FILE *f1, *f2;
    int a, b, i, j, f = -1;
    int ca;
    int g=0, B;
    long long r, pas;
    r=0;
    f1=fopen("gfact.in","r");
    fscanf(f1,"%d%d",&a,&b);
    fclose(f1);
    i=a/2;
    while(f==-1&&i>=2){
        if(a%i==0){
            j=2;
            while(j*j<=i && i%j != 0)
                j++;
            if(j*j>i)
                f=i;
        }
        i--;
    }
    if(f==-1)
        Pn=a;
    else
        Pn=f;
    ca=a;
    while(ca>=Pn){
        ca/=Pn;
        g++;
    }
    B = b*g;
    pas=1LL<<L;
    while(pas!=0){
        if(q(pas+r)<B)
            r+=pas;
        pas/=2;
    }
    f2=fopen("gfact.out","w");
    fprintf(f2,"%lld",r+1);
    fclose(f2);
    return 0;
}