#include <fstream>
#include <cstring>
#include <cmath>

#define maxD 1064

using namespace std;

ifstream in;
ofstream out;

int d[maxD];

long long P;

inline long long pinex(long long A)
{
    int powN=(1<<d[0]);
    long long sol=A;

    for(int i=1;i<powN;++i)
    {
        long long p=1;
        int b=0;
        for(int cnt=1,j=i;j;j>>=1,++cnt)
            if(j&1) p*=d[cnt],++b;
        if(b&1) p*=-1;
        sol+=A/p;
    }

    return sol;
}

int main()
{
    long long N;

    in.open("frac.in");

    in>>N>>P;

    in.close();

    memset(d,0,sizeof(d));

    if(N%2==0)
    {
        d[++d[0]]=2;
        while(N%2==0) N/=2;
    }

    double sN=sqrt(N);
    for(int i=3;i<=sN;i+=2)
        if(N%i)
        {
            d[++d[0]]=i;
            while(N%i==0) N/=i;
        }
    if(N!=1) d[++d[0]]=N;

    long long num=0;
    long long L=1;
    long long R=(1LL<<61);

    while(L<=R)
    {
        long long M=L+((R-L)>>1);
        long long cnt=pinex(M);

        if(P<=cnt)
        {
            num=M;
            R=M-1;
        }
        else L=M+1;
    }

    out.open("frac.out");

    out<<num<<'\n';

    out.close();

    return 0;
}