#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
#define MAX 10000002
#define int unsigned long long
using namespace std;
bool ciur[MAX];
int n,p;
vector<int> prime;
vector<int> divv;

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

int f(int a){
    /// cate nr sunt prime cu n si sunt mai mici sau egale decat a
    int x = divv.size();
    int ans = 0;
    for(int i = 1; i < (1<<x); i++){
        int subm = 1;
        for(int j = 0; j < x; j++){
            if(i&(1<<j)){
                subm *= 1ULL*divv[j];
            }
        }
        if(__builtin_popcount(i)%2){
            ans += a/subm;
        }else{
            ans -= a/subm;
        }
    }
    return a-ans;
}

signed main()
{
    fin >> n >> p;
    int rad = sqrt(n);
    for(int i = 2; i <= rad; i++){
        if(ciur[i] == 0){
            prime.push_back(i);
            for(int j = i+i; j <= rad; j += i){
                ciur[j] = 1;
            }
        }
    }
    int ind = 0;
    while(n > 1 && prime[ind]*prime[ind] <= n && ind < prime.size()){
        if(n%prime[ind] == 0){
            divv.push_back(prime[ind]);
            while(n%prime[ind] == 0){
                n /= prime[ind];
            }
        }
        ind++;
    }
    if(n > 1){
        divv.push_back(n);
    }
    int st = 1, dr = (1ULL<<61);
    int ans = 0;
    /// 0 0 0 0 1 1 1 1
    ///         ^
    while(st <= dr){
        int mid = (st+dr)/2;
        if(f(mid) >= p){
            ans = mid;
            dr = mid-1;
        }else{
            st = mid+1;
        }
    }
    fout << ans;
    return 0;
}