#include <iostream>
#include <fstream>
#include <bitset>
#include <cmath>

using namespace std;

ifstream in ("frac.in");
ofstream out ("frac.out");
long long const limup = 1LL<<61;
/*
bitset <110000> ciur;
void precompute(){
  ciur[0] = 1;
  ciur[1] = 1;
  for(i = 4 ; i <= 110000 ; i += 2){
    ciur[i] = 1;
  }
  for(i = 3 ; i < 110000 ; i += 2){
    if(ciur[i] == 0){
      for(j = i *i ; j < 110000 ; j+= i){
        ciur[j] = 1;
      }
    }
  }
}
*/
long long factor[100];
long long nfactor = 0 ,lim = 0;
void descompunere(long long n){
  nfactor = 0;
  lim = sqrt(n);
  if(n % 2 == 0){
    factor[0] = 2;
    nfactor = 1;
    while(n % 2 == 0){
      n /= 2;
    }
  }
  long long   h = 3;
  while(1 < n && h <= lim){
    if(n % h == 0){
      factor[nfactor] = h;
      nfactor++;
      while(n % h == 0){
        n /= h;
      }
    }
    h += 2;
  }
  if(1 < n){
    factor[nfactor] = n;
    nfactor++;
  }
}
long long nr ,rez = 0;
void number(long long   i ,long long acumulator ,long long   y){
  long long   j;
  if(i == nfactor){
    if(y % 2 == 1){
      rez -= nr / acumulator;
    } else
      rez += nr / acumulator;
  }
  for(j = i ; j < nfactor ; j++){
    number(j + 1,acumulator * factor[i] ,y + 1);
  }
}
long long  verif(long long n){
  rez = nr = n;
  long long  i ;

  for(i = 0 ; i < nfactor ; i++){
    number(i,1,0);
  }

  return rez;
}
int main(){
  long long  n , p ,st = 0 ,dr = limup ,mid = 0 ,aux = 0;
  //precompute();
  in>>n>>p;
  descompunere(n);
  mid = (st + dr) /2;
  while(true){
    aux = verif(mid);
    if(aux == p){
      if(verif(mid - 1) < p){
        out<<mid;
        return 0;
      } else{
        dr = mid - 1;
      }
    } else if(aux < p){
      st = mid + 1;
    } else{
      dr = mid;
    }
    mid = (st + dr) /2;
  }
  return 0;
}