#include <bits/stdc++.h>
#define MAXFACT 10

using namespace std;

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

long long fact[MAXFACT];
int sz_fact;

void make_fact(long long n){
    int d;

    sz_fact = 0;
    d = 2;
    while((long long)d * d <= n){
        if(n % d == 0){
            fact[sz_fact++] = d;
            do{
                n /= d;
            }while(n % d == 0);
        }
        d++;
    }
    if(n > 1){
        fact[sz_fact++] = d;
    }
}

long long get_X(long long x){//pt un numar x, al catelea este prim cu n
    long long rez, nr;
    int mask, i, bit1;

    rez = x;
    for(mask = 1; mask < (1 << sz_fact); mask++){
        bit1 = 0;//cati factori luam
        nr = 1;
        for(i = 0; i < sz_fact; i++){
            if(((mask >> i) & 1) == 1){
                bit1++;
                nr *= fact[i];
            }
        }

        rez = rez + (bit1 % 2 == 0 ? 1 : -1) * (x / nr);
//        printf("mask = %d, bit1 = %d, nr = %d, rez = %d\n", mask, bit1, nr, rez);
    }
    return rez;
}

int main()
{
    long long n, cn, p, st, dr, mij;
    int d;

    cin >> n >> p;

    make_fact(n);
//    printf("cati = %d\n", get_X(9));


    //cb_francu-lower_bound (st, dr]
    st = 1;
    dr = ((long long)1 << 61);
    while(dr - st > 1){
        mij = (st + dr) / 2;

//        printf("test:\n");
        if(get_X(mij) >= p){
            dr = mij;
        }else{
            st = mij;
        }
    }
    cout << dr << "\n";
    return 0;
}