#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const i64 SB = 1LL<<61;

int nfs;
i64 n, p;
i64 pfs[25];

void factorize(i64 arg) {
    i64 i = 3;

    if(~arg&1) {
        while(~arg&1)
            arg>>=1;
        pfs[nfs++] = 2;
    }

    while(i*i<=arg) {
        if(arg%i) {
            i+=2;
            continue;
        }
        while(!(arg%i))
            arg/=i;
        pfs[nfs++] = i;
        i+=2;
    }
    if(arg>1)
        pfs[nfs++] = arg;
}

bool check(i64 lim) {
    i64 m_lim, tmp, ans;
    int bits;

    m_lim = 1LL<<nfs;
    ans   = lim;

    for(int i=1; i<m_lim; ++i) {
        tmp  = 1;
        bits = 0;
        for(int j=0; (1LL<<j)<=i; ++j) {
            if(i&(1LL<<j)) {
                tmp*=pfs[j];
                ++bits;
            }
        }
        if(bits&1)
            ans-=lim/tmp;
        else
            ans+=lim/tmp;
    }
    return ans>=p;
}

int main(void) {
    FILE *fi = fopen("frac.in", "r");
    FILE *fo = fopen("frac.out", "w");
    i64 ans;

    fscanf(fi,"%lld%lld",&n,&p);

    factorize(n);
    ans = 0;

    for(i64 m=SB; m; m>>=1)
        if(!check(ans+m))
            ans+=m;

    fprintf(fo,"%lld\n",++ans);

    fclose(fi);
    fclose(fo);
    return 0;
}