#include <iostream>
#include <algorithm>
#include <fstream>


using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");

unsigned long long n,p,catidivprimi,v[50],st,dr,mij,val,rasp,cnt,aux,ci,sol,afis,i,d,j;

int main()
{
	f>>n>>p;
	if(n%2==0)
    {v[++catidivprimi]=2;
        while(n%2==0)
        {
            n/=2;
        }
    }
    for( d=3;d*d<=n;d+=2)
    {
        if(n%d==0)
        {
            v[++catidivprimi]=d;
            while(n%d==0)
            {
                n/=d;
            }
        }
    }
    if(n>1)
    {
        v[++catidivprimi]=n;
    }

val=1LL<<catidivprimi;

    st=1;
    dr=1LL<<61;
   while(st<=dr)
   {
       mij=(st+dr)/2;
       sol=0;
       for( i=1;i<val;i++)
       {cnt=0;
       aux=1;
       ci=i;

           for( j=catidivprimi;j>=1;j--)
           {
               if(ci%2==1) {aux*=v[j];cnt++;}
               ci/=2;
           }
           if(cnt%2==1)
           {
               sol+=mij/aux;

           }
           else sol-=mij/aux;
       }
       rasp=mij-sol;
       if(rasp>=p)
       {
           if(rasp==p) afis=mij;
           dr=mij-1;
       }
       else st=mij+1;
   }
 g<<afis;




}