#include <fstream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;

ifstream cin("frac.in");
ofstream cout("frac.out");

long long n, p;
int ciur[1000005];
vector<int> primes;

void precalc(){
    for(int i=2;i<=1000000;i++){
        ciur[i]=true;
    }
    for(int i=2;i<=1000000;i++){
        if(ciur[i]==true){
            for(int j=2*i;j<=1000000;j+=i){
                ciur[j]=false;
            }
            primes.push_back(i);
        }
    }
}

vector<long long> get_fact(long long x){
    vector<long long> ans;
    int d=0;
    while(d<primes.size()&&primes[d]*primes[d]<=x){
        if(x%primes[d]==0){
            ans.push_back(primes[d]);
            while(x%primes[d]==0){
                x=x/primes[d];
            }
        }
        d++;
    }
    if(x>1){
        ans.push_back(x);
    }
    return ans;
}

long long query(long long a, long long b){
    vector<long long> primes=get_fact(b);
    int k=primes.size();
    long long ans=0;
    for(int mask=0;mask<(1<<k);mask++){
        long long p=1;
        int cnt=0;
        for(int j=0;j<k;j++){
            if(mask&(1<<j)){
                p=p*primes[j];
                cnt++;
            }
        }
        if(cnt%2==0){
            ans+=a/p;
        }
        else{
            ans-=a/p;
        }
    }
    return ans;
}

int main(){
    precalc();
    cin>>n>>p;
    long long st=1, dr=(1LL<<61), mij=0, ans=0;
    while(st<=dr){
        mij=(st+dr)/2;
        if(query(mij, n)<p){
            st=mij+1;
        }
        else{
            ans=mij;
            dr=mij-1;
        }
    }
    cout<<ans;
}