#include<fstream>
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
#include <vector>
#include <queue>
#include <deque>

#define DIM 1000

using namespace std;

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

//ifstream f("in.in");
//ofstream g("out.out");

long long n,p;
long long d,k,v[DIM+5];
bool u[DIM+5];

bool sol(long long m){
    //cout<<m<<" ";
    memset(u,0,sizeof(u));

    long long nr=0,i,cnt,prod;
    while(u[0] == 0){
        ///generare
        i = k;
        while(u[i] == 1){
            u[i] = 0;
            i--;
        }
        if(i == 0){
            break;
        }
        u[i] = 1;

        cnt=0;prod=1;
        for(long long j=1;j<=k;j++){
            if(u[j] == 1){
                prod*=v[j];
                cnt++;
            }
        }

        ///includere/excludere
        //cout<<"|"<<p<<"|";
        if(cnt != 0){
            if(cnt%2 == 1){
                nr+=m/prod;
            }else{
                nr-=m/prod;
            }
        }
    }
    nr = m - nr;
    //cout<<nr<<"-"<<p<<" (";
    if(nr>=p){
        //cout<<"1)\n";
        return 1;
    }
    //cout<<"0)\n";
    return 0;
}

int main(){

    f>>n>>p;

    d = 2;
    while(d*d<=n && n!=1){
        if(n%d == 0){
            k++;
            v[k] = d;
            while(n%d == 0){
                n/=d;
            }
        }
    }
    if(n!=1){
        k++;
        v[k] = n;
    }

    long long st=1,dr=(1LL<<61),mid,solNr;
    while(st<=dr){
        mid = (st+dr)/2;
        //cout<<mid<<": ";
        if(sol(mid) == 1){
            solNr = mid;
            dr = mid-1;
        }else{
            st = mid+1;
        }
    }
    g<<solNr;

    f.close();
    g.close();
    return 0;
}