#include <stdio.h>
int d[ 12 ], ind = 0;

void descomp ( int n ){
  int i;
  for ( i = 2; i * i <= n; i++ ){
    if ( n % i == 0 ){
        d[ ind ] = i;
        ind++;
    }
    while ( n % i == 0 )    n /= i;
  }
  if ( n > 1 ){
    d[ ind ] = n;
    ind++;
  }
  return ;
 }

long long nrfr(long long x){
  int i, ci, minus, p;
  long long nr, rez = 0;
  for(i = 1; i < (1 << ind); i++){
    nr = 1;
    minus = -1;
    p = 0;
    for(ci = i; ci > 0; ci >>= 1){
      if(ci & 1){
        nr *= d[p];
        minus = -minus;
      }
      p++;
    }
    rez += minus * (x / nr);
  }
  return x - rez;
}

long long caut ( long long p ){
  long long i = 0, pas = 1LL * (1 << 30) * (1 << 30) * 2;
  while ( pas > 0 ){
    if(nrfr(i + pas) < p)   i += pas;
    pas >>= 1;
  }
  return i + 1;
}

int main()
{
  FILE *in = fopen( "frac.in", "r" );
  long long n, p;
  fscanf( in, "%lld%lld", &n, &p );
  fclose( in );
  FILE *out = fopen( "frac.out", "w" );
  descomp( n );
  fprintf( out, "%lld", caut ( p ) );
  fclose( out );
  return 0;
}