#include <bits/stdc++.h>

using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
const long long range_max = 1LL << 61;
long long p;
long long fp[15];
int k;
long long calc(long long n){
    long long rez = n;
    for(int e = 1; e < (1 << k); e++){
        long long t = 1;
        int nrb = 0;
        for(int i = 0; i < k; i++){
            if((1 << i) & e){
                t *= fp[i];
                nrb++;
            }
        }
        if(nrb & 1) rez -= n / t;
        else rez += n / t;
    }
    return rez;
}
int cb(){
    long long st = 1, dr = range_max + 5, med, poz = 0;
    while(st <= dr){
        med = (st + dr) / 2;
        if(calc(med) >= p){
            poz = med;
            dr = med - 1;
        }
        else st = med + 1;
    }
    return poz;
}
int main()
{
    long long n,x,d = 3;
    fin >> n >> p;
    x = n;
    if(x % 2 == 0){
        fp[k++] = 2;
        while(x % 2 == 0) x /= 2;
    }
    while(x > 1){
        if(x % d == 0){
            fp[k++] = d;
            while(x % d == 0) x /= d;
        }
        if(d * d > x) d = x;
        else d += 2;
    }
    fout << cb();
    return 0;
}