//#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
using namespace std;
ifstream ka("frac.in");
ofstream ki("frac.out");

const int SQRT_MAX = 109545;

long long n, p;
bool compus[SQRT_MAX + 1];
long long primi[SQRT_MAX + 1], fact[SQRT_MAX + 1];
int marime;

long long binara()
{
    long long inc = 1, sf = (1LL << 61);
    while(inc < sf)
    {
        long long mij = (inc + sf) / 2;
        long long rez = mij;
        long long t = fact[0];
        for(int i = 1; i < (1 << t); i++)
        {
            long long nr = 0, prod = 1;
            for(int j = 0; j < t; j++)
                if(i & (1 << j))
                {
                    prod = 1LL * prod * fact[j + 1];
                    nr++;
                }
            if(nr % 2 == 1)
                nr = -1;
            else
                nr = 1;
            rez += 1LL * nr * mij / prod;
        }
        //cout << mij << " " << rez << '\n';
        if(rez < p)
            inc = mij + 1;
        else if(rez > p)
            sf = mij - 1;
        else if(rez == p)
            sf = mij;
    }
    return inc;
}

int main()
{
    ka >> n >> p;
    primi[++marime] = 2;
    for(int i = 3; i <= SQRT_MAX; i += 2)
    {
        if(!compus[i])
        {
            primi[++marime] = i;
            for(long long j = (long long)i * i; j <= SQRT_MAX; j += i)
                compus[j] = true;
        }
    }
    fact[0] = 0;
    for(int i = 1; i <= marime; i++)
        if(n % primi[i] == 0)
        {
            fact[++fact[0]] = primi[i];
            while(n % primi[i] == 0)
                n /= primi[i];
        }
    if(n > 1)
        fact[++fact[0]] = n;
    ki << binara();
}