#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
const int NMAX = 1e6;
bool ciur[NMAX+5];
int prime[80005];
long long v[15];
bool F(unsigned long long a,unsigned long long p,int fact){
    unsigned long long nr=0;
    int p2=(1<<fact);
    for(int i=1;i<p2;i++){
        int ci=i,acum=1,ok=0,biti=-1;unsigned long long prod=1;
        while(ci>0){
            if(ci&1){
                prod*=v[acum];biti*=-1;
            }
            ci/=2;acum++;
        }
        if(ok==0){
            unsigned long long ceva=a/prod;
            nr+=1ULL*biti*ceva;
        }
    }
    unsigned long long rez=a-nr;
    if(rez<p){return 1;}
    return 0;
}
int main()
{
    ciur[0]=ciur[1]=1;
    for(int i=2;i*i<=NMAX;i++){
        if(ciur[i]==0){
            for(int j=i*i;j<=NMAX;j+=i){
                ciur[j]=1;
            }
        }
    }
    int pp=0;
    for(int i=1;i<=NMAX;i++){
        if(ciur[i]==0){
            pp++;prime[pp]=i;
        }
    }
    unsigned long long n,p;fin>>n>>p;
    int poz=1,d=2,cnt=0,fact=0;
    while(n>1&&1ULL*d*d<=n){
        cnt=0;
        while(n%d==0){
            cnt++;n/=d;
        }
        if(cnt>0){
            fact++;v[fact]=d;
        }
        poz++;d=prime[poz];
    }
    if(n>1){
        fact++;v[fact]=n;
    }
    unsigned long long st=0,dr=LLONG_MAX,mij,val=-1;
    while(dr>=st){
        mij=st+(dr-st)/2;
        if(F(mij,p,fact)==1){
            val=mij;st=mij+1;
        }
        else{
            dr=mij-1;
        }
    }
    fout<<val+1<<'\n';
    return 0;
}