#include <bits/stdc++.h>
#define ULL unsigned long long

using namespace std;

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

ULL nr=(1<<31),n,p;
ULL Div[30],nrDiv;

ULL totalNr(ULL nr)
{
    ULL sum=nr;
    int fin=(1<<nrDiv);

    for(int i=1;i<=fin-1;i++)
    {
        ULL dvr=1;
        int nrI=0;

        for(int j=0;j<nrDiv;j++)
            if( i&(1<<j) )
            {
                nrI++;
                dvr*=Div[j+1];
            }

        if(nrI%2)
            sum-=nr/dvr;
        else
            sum+=nr/dvr;
    }

    return sum;
}

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

    int rad=sqrt(n);
    for(int i=2;i<=rad && n!=1;i++)
        if(n%i==0)
        {
            Div[++nrDiv]=i;

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

    if(n>1)
        Div[++nrDiv]=n;

    for(ULL pas=nr-1;pas;pas/=2)
        while(nr>pas && totalNr(nr-pas)>=p)
            nr-=pas;

    out<<nr;

    return 0;
}