#include <bits/stdc++.h>

using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
#define int long long
int n, k, lung;
vector<int> divs;

inline int check(int x) {
    ///numara cate nr sunt <= x si neprime cu n
    int prime = 0;
    for(int mask=1; mask < (1 << lung); mask++) {
        int prod = 1, cntBiti = 0;
        for(int i=0; i<lung; i++)
            if(mask & (1 << i)) prod *= divs[i], cntBiti++;
        if(cntBiti % 2 == 1) prime += x / prod;
        else prime -= x / prod;
    }
    int neprime = x - prime;
    return neprime >= k;
}

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

    return 0;
}