#include <fstream>
#include <vector>

using namespace std;

#define int long long

ifstream in("frac.in");
ofstream out("frac.out");
int n, p;
vector<int> v;

int check(int x)
{
    int stmax = (1 << (v.size()));
    int rez = 0;

    for(int mask = 1; mask < stmax; mask++)
    {
        int cnt = 0;
        int prod = 1;

        for(int i = 0; i<v.size(); i++)
        {
            if((mask & (1 << i)))
            {
                cnt++;
                prod *= v[i];
            }
        }

        if(cnt % 2 == 1)
        {
            rez += x / prod;
        }
        else
        {
            rez -= x / prod;
        }
    }

    return rez;
}

signed main()
{
    in>>n>>p;

    for(int i = 2; i*i<=n; i++)
    {
        if(n % i == 0)
        {
            v.push_back(i);

            while(n % i == 0)
            {
                n /= i;
            }
        }
    }

    if(n > 1)
    {
        v.push_back(n);
    }

    /*for(auto it: v)
    {
        out<<it<<" ";
    }*/

    int st = 1;
    int dr = (1LL << 61);
    int ans;

    while(st <= dr)
    {
        int mij = (st + dr) / 2;

        int x = check(mij);
        if(mij - x == p)
        {
            ans = mij;
            dr = mij - 1;
        }
        else if(mij - x < p)
        {
            st = mij + 1;
        }
        else if(mij - x > p)
        {
            dr = mij - 1;
        }
    }

    out<<ans;

    return 0;
}