#include <bits/stdc++.h>

using namespace std;
#define int long long
ifstream in("frac.in");
ofstream out("frac.out");
vector<int> v;
bool cate(int nr,int goal)
{
    int nr1=(1<<(v.size()-1))-1;
    int ans=nr;
    for(int i=1; i<=nr1; i++)
    {
        int ra=__builtin_popcount(i);
        int prod=1;
        for(int j=0; (1<<j)<=i; j++)
        {
            int y=(1<<j);
            int val=y&i;
            if(val==y)
            {
                prod=prod*v[j+1];
            }
        }
        if(ra%2==1)
        {
            ans-=nr/prod;
        }
        else
        {
            ans+=nr/prod;
        }
    }
    if(ans>=goal)
    {
        return 1;
    }
    if(ans<goal)
    {
        return 0;
    }
}
signed main()
{
    int n,p;
    in>>n>>p;
    int prime1=n;
    v.push_back(0);
    if(prime1%2==0)
    {
        v.push_back(2);
        while(prime1%2==0)
        {
            prime1=prime1/2;
        }
    }
    for(int i=3; i*i<=prime1; i=i+2)
    {
        if(prime1%i==0)
        {
            v.push_back(i);
            while(prime1%i==0)
            {
                prime1=prime1/i;
            }
        }
    }
    if(prime1>1)
    {
        v.push_back(prime1);
    }
    int l=1,r=1e18;
    int an=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int nr=cate(mid,p);
        if(nr==1)
        {
            an=mid;
            r=mid-1;
        }
        else if(nr==0)
        {
            l=mid+1;
        }
    }
    out<<an;
    return 0;
}