#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <cstring>
#include <stack>
#include <cmath>
#include <queue>
#include <fstream>

using namespace std;

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

const int ciur_dim = 1000000;

vector <int> prime;
vector <long long int> factori;
int k,st[ciur_dim],semn;
bool ciur[ciur_dim];
long long int prod,n,sol,p,a,b;

void Fa_Ciur()
{
    int i,j;
    for (i=2; i<ciur_dim; i++)
    {
        if (ciur[i] == 0)
        {
            prime.push_back(i);
            for (j=2*i; j<ciur_dim; j += i)
            {
                ciur[j] = 1;
            }
        }
    }
}

void Afisare()
{
    prod = 1;
    for (int i=1; i<=k; i++)
    {
        prod *= factori[st[i]];
    }
    sol = sol + semn*a/prod;
}


void Back(int top)
{
    if (top == k)
    {
        Afisare();
    }
    else
    {
        for (int i = st[top]+1; i<=n-k+top; i++)
        {
            st[top+1] = i;
            Back(top+1);
        }
    }
}

long long int Rezolva()
{
    int it = 0,i;
    sol = 0;
    n = factori.size();
    for (i=1; i<=n; i++)
    {
        k = i;
        if ((i-1)%2 == 0)
        {
            semn = 1;
        }
        else
            semn = -1;
        Back(0);
    }
    return (a-sol);
}

int main()
{
    in >> n >> p;
    Fa_Ciur();
    b = n;
    factori.push_back(0);
    int it = 0;
    while (b > 1)
    {
        if (b%prime[it] == 0)
        {
            factori.push_back(prime[it]);
            while (b%prime[it] == 0)
            {
                b /= prime[it];
            }
        }
        if (prime[it] > sqrt(b) && b != 1)
        {
            factori.push_back(b);
            b = 1;
        }
        it++;
    }
    long long int st = 1,acum;
    long long int dr = 1e14;
    long long int mij,solprob;
    while (st <= dr)
    {
        mij = st + (dr-st)/2;
        a = mij;
        acum = Rezolva();
        if (acum >= p)
        {
            solprob = mij;
            dr = mij-1;
        }
        else st = mij+1;
    }
    out << solprob;
    return 0;
}