#include <iostream>
#include <fstream>
#define LL long long int
using namespace std;

LL N,P,f[50],K,aux=1,A,SUM;

void comb(int cnt, int ind){
    if (cnt==0){
        SUM+=A/aux;
        return;
    }

    if (K-ind+1>cnt)
        comb(cnt,ind+1);
    aux*=f[ind];
    comb(cnt-1,ind+1);
    aux/=f[ind];
}

LL sum(LL nr){
    A=nr;
    int i; LL res=0;
    for (i=1; i<=K; i++){
        SUM=0;
        comb(i,1);
        if (i%2) res+=SUM;
        else res-=SUM;
    }

    return A-res;
}

int main(){
    ifstream fin("frac.in");
    ofstream fout("frac.out");
    fin >> N >> P;

    LL l=1,r=(1LL<<62),i,mid,s;
    for (i=2; i*i<=N; i++)
        if (N%i==0){
            f[++K]=i;
            while (N%i==0) N/=i;
        }

    if (N!=1) f[++K]=N;

    while (r-l>1){
        mid=(l+r)/2;
        s=sum(mid);
        if (s<=P-1) l=mid;
        else r=mid-1;

    }
    if (sum(l+1)==P-1) l++;

    fout << l+1;

    return 0;
}