#include <bits/stdc++.h>
#define maxb (1<<17)
typedef long long ll;
using namespace std;
ll B,K,P[1<<14],p,C[maxb],D[100],d,num,k,rs,ans;

bool check(ll A){
    rs=0;
    for(int b=1;b<(1<<d);b++){
        k = 0;num=1;
        for(int i = 0;i<d;i++) if((1<<i)&b){num*=D[i];k++;}
        rs+=(A/num)*(k%2 ? 1 : -1);
    }

    return A-rs>=K;
}

int main() {
	ifstream cin("frac.in");
	ofstream cout("frac.out");
    cin >> B >> K;
    for(int i = 2;i<maxb;i++) if(!C[i]){
        P[++p] = i;
        for(int j = i+i;j<maxb;j+=i) C[j] = 1;
    }
    
    d = 0;
    for(int i = 1;P[i]<=sqrt(B);i++) if(B%P[i]==0){
        D[d++] = P[i];
        while(B%P[i] == 0) B/=P[i];
    } 
    if(B>1) D[d++] = B;
    
    ll st=1,dr=(1LL<<61);
    while(dr-st>3){
        ll mid=(dr+st)/2;
        if(check(mid)) dr = mid;
        else st = mid+1;
    }
    for(;st<=dr;st++) if(check(st)) return cout << st,0;
}