#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;

ll n,k;
int a[500],pr;

void fact() {
    int p=2;
    while (p*p<=n && n>1) {
        if (n%p==0) {
            a[++pr]=p;
            while (n%p==0) n/=p;
        }
    }
    if (n>=2) a[++pr]=n;
}

bool OK(ll N) {
    ll rs=0;
    for (int i=1; i<(1<<pr); ++i) {
        int k2=0, nr=1;
        for (int j=0; (1<<j)<=i; ++j) {
            if (i & (1<<j)) {
                ++k2, nr*=a[j+1];
            }
        }
        rs+=N/nr*(k2%2?1:-1);
    }
    return  N-rs>=k;
}

int main() {
    ifstream cin("frac.in");
    ofstream cout("frac.out");
    cin>>n>>k;
    fact();

    ll st=1, dr=(1LL<<61);
    while (st<=dr) {
        ll mid=(st+dr)/2;
        if (OK(mid)) dr=mid-1;
        else st=mid+1;
    }
    cout<<dr+1;

    return 0;
}