#include<fstream>
#include<iostream>
#include<bitset>
#define DIM 10000000
using namespace std;
long long n, b, p, u, mid, aux;
int nrp, f[40], pr[40], i, j, x;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long verif(long long a){
    int i, nr;
    long long prod, r;
    r = 0;
    for(i = 0; i <= x; i++){
        f[i] = 0;
    }
    f[x] = 1;
    while(f[0] == 0){
        prod = 1;
        nr = 0;
        for(i = 1; i <= x; i++){
            if(f[i] == 1){
                prod *= pr[i];
                nr++;
            }
        }
        i = x;
        while(f[i] == 1){
            f[i] = 0;
            i--;
        }
        f[i] = 1;
        if(nr % 2 == 1){
            r += a / prod;
        }
        else{
            r -= a / prod;
        }
    }
    return a - r;
}
int main(){
    fin>> b >> n;
    aux = b;
    for(i = 2; (long long) i * i <= b && aux != 1; i++){
        if(aux % i == 0){
            pr[++x] = i;
            while(aux % i == 0){
                aux /= i;
            }
        }
    }
    if(aux != 1){
        pr[++x] = aux;
    }
    p = 1;
    u = (1LL << 62);
    while(p <= u){
        mid = (p + u) / 2;
        long long tmp = verif(mid);
        if(tmp >= n){
            u = mid - 1;
        }
        else{
            p = mid + 1;
        }
    }
    fout<< p <<"\n";
    return 0;
}