#define boostIO ios_base::sync_with_stdio(false); fin.tie(nullptr); fout.tie(nullptr);
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>

using namespace std;

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

long long n, p;

int e;
vector <long long> divizor;

void check(long long &number, long long maybeDivizor){
    int exponent = 0;
    while(number % maybeDivizor == 0){
        exponent++;
        number /= maybeDivizor;
    }
    if(exponent != 0)
        divizor.push_back(maybeDivizor);
}

void get_divizors(long long x){
    divizor.clear();
    check(x, 2);
    check(x, 3);
    for(int i=5; i<=x/i; i+=6){
        check(x, i);
        check(x, i+2);
    }
    if(x != 1)
        check(x, x);
}

long long pinex(long long limit){
    long long number, total = 0;
    int semn;
    for(int mask=1; mask < (1 << (int)divizor.size()); mask++){

        if(__builtin_popcount(mask)&1)
            semn = 1;
        else
            semn = -1;

        number = 1;
        for(int i=0; i < (int)divizor.size(); i++)
            if(mask & (1 << i))
                number *= divizor[i];

        total += semn * (limit / number);
    }
    return limit - total;
}

int main (){
    boostIO

    fin>>n>>p;
    get_divizors(n);

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

        if(pinex(md) >= p)
            dr = md - 1;
        else
            st = md + 1;
    }
    fout<<st;
    return 0;
}
/**
12 = 2^2 * 3^1

1 2 3 4 5 6 7 8 9 10 11 12
Y N N N Y N Y N N  N  Y  N
**/