#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define LL long long

using namespace std;

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

const int LIMIT = 1e6;
bitset <LIMIT + 5> ciur;
int p, prime[80005];
void mark(int num){
    for(int i=num*num; i<=LIMIT; i+=num)
        ciur[i] = true;
}

LL n, k, cpy, st, md, dr, sol;
LL dcnt, d[70];

LL pinex(LL limit){
    LL answer = 0;
    LL prod, part;
    for(LL mask=1; mask < (1 << dcnt); mask++){
        prod = 1;
        part = 0;

        for(int i=0; i < dcnt; i++)
            if(mask & (1<<i)){
                prod *= d[i];
                part++;
            }

        if(part&1)
            answer += limit / prod;
        else
            answer -= limit / prod;
    }
    return limit - answer;
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    ciur[0] = ciur[1] = 1;
    mark(2);
    mark(3);
    for(int i=5; i<=LIMIT/i; i+=6){
        if(!ciur[ i ]) mark( i );
        if(!ciur[i+2]) mark(i+2);
    }
    prime[++p] = 2;
    prime[++p] = 3;
    for(int i=5; i<=LIMIT; i+=6){
        if(!ciur[ i ]) prime[++p] = i;
        if(!ciur[i+2]) prime[++p] = i+2;
    }

    fin>>n>>k;

    cpy = n;
    for(int i=1; i<=p && prime[i]<=cpy/prime[i]; i++)
        if(cpy % prime[i] == 0){
            d[dcnt++] = prime[i];
            while(cpy % prime[i] == 0)
                cpy /= prime[i];
        }
    if(cpy > 1)
        d[dcnt++] = cpy;

    st = 1;
    dr = (1LL << 61);
    while(st <= dr){
        md = (dr - st) / 2 + st;

        if(pinex(md) >= k){
            sol = md;
            dr = md - 1;
        }else
            st = md + 1;
    }
    fout<<sol;
    return 0;
}