#include<bits/stdc++.h>
#define int long long

using namespace std;

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

int n , k , lun;
vector<int> divs;

inline int check(int x){
    int prime = 0;
    for(int mask = 1 ; mask < (1 << lun) ; mask++){
        int prod = 1 , cntbiti = 0;
        for(int i = 0 ; i < lun ; i++){
            if(mask & (1 << i)) prod *= divs[i] , cntbiti++;
        }
        if(cntbiti % 2 == 1) prime += x / prod;
        else prime -= x / prod;
    }
    int neprim = x - prime;
    return neprim >= k;
}

signed main(){
    fin >> n >> k;
    int d = 2;
    while(n > 1){
        if(n % d == 0){
            divs.push_back(d);
            while(n % d == 0) n /= d;
        }
        d++;
        if(d * d > n) d = n;
    }
    lun = divs.size();
    int st = 1 , dr = 1e7 , sol;
    while(st <= dr){
        int mid = (st + dr) / 2;
        if(check(mid)){
            sol = mid;
            dr = mid - 1;
        }
        else st = mid + 1;
    }
    fout << sol;
}