#include <bits/stdc++.h>

using namespace std;

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

bool verif(int fact, int p, int q) {
    int sum=0, cp=p;
    while(fact/p>0) {
        sum+=(fact/p);
        p=p*cp;
    }
    if(sum>=q) {
        return true;
    } else {
        return false;
    }
}

int main()
{
    int p, q, divmax=2, dv=2;
    fin >> p >> q;
    while(p!=1) {
        while(p%dv==0) {
            divmax=dv;
            p/=dv;
        }
        dv++;
        if(dv*dv>p) {
            dv=p;
        }
    }
    p=divmax;

    long long l=1, r=INT_MAX, mid, sol=-1;
    if(p==1) {
        fout << "0";
    } else {
        while(l<=r) {
            mid=(l+r)/2;
            if(verif(mid, p, q)) {
                r=mid-1;
                sol=mid;
            } else {
                l=mid+1;
            }
        }
        fout << sol;
    }
    return 0;
}