#include <bits/stdc++.h>

using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
unsigned long long int a, b, c;
vector <long long int> d;

void divprim(long long x)
{
    d.clear();
    for(long long int i=2; i*i<=x; i++)
    {
        if(x%i==0)
        {
            d.push_back(i);
            while(x%i==0)
            {
                x/=i;
            }
        }
    }
    if(x>1)
    {
        d.push_back(x);
    }
}

void backtrack(int index, unsigned long long dc, int poz, unsigned long long urm)
{
    if(index>0)
    {
        if(index%2==0)
        {
            c=c-urm/dc;
        }
        else
        {
            c=c+urm/dc;
        }
    }
    for(int i=poz+1; i<d.size(); i++)
    {
        dc=dc*d[i];
        backtrack(index+1, dc, i, urm);
        dc/=d[i];
    }
}

int main()
{
    /// a p-a fractie ireductibila cu numitorul N.
    ///scriem fractiile in ordince crescatoare in fct de numarator si daca o vrem pe a p-a folosim pinex, si vedem al p-lea
    ///nr care este mai mic decat n si prim cu el
    ///daca avem sa zicem numitorul n si un numar x si vrem sa spunem cate numere pana in x sunt prime intre ele cu n
    ///nu putem sa trecem prin toate numerele si rezultatul poate chiar sa depaseasca n, deci nu putem sa iteram prin toti x
    ///putem mai eficient sa facem un p(n, x)
    ///daca avem un y<x => p(n, y)<p(n, x)
    ///daca avem y>x => p(n, y)>p(n, x)
    ///la un moment dat p(n, x) atinge valoarea cautata si putem sa cautam binar
    ///cautam binar
    ///calculam p(n, mid) si daca p(n, mid)<P, atunci crestem stanga
    ///daca p(n, mid)>P, atunci scadem dreapta
    fin>>a>>b;
    divprim(a);
    unsigned long long st=1, dr=LLONG_MAX;
    while(st<=dr)
    {
        unsigned long long int mid = (st + dr) / 2;
        c = 0;
        backtrack(0, 1, -1, mid);
        unsigned long long int nr = mid - c;
        if (nr < b)
        {
            st=mid+1;
        }
        else
        {
            dr=mid-1;
        }
    }
    fout<<st;
    return 0;
}