#include <stdio.h>
#include <stdint.h>

void read_int64_t(FILE *__restrict stream, int64_t *__restrict nr) {
  uint8_t ch;
  *nr = 0;
  while ((ch = fgetc(stream)) && ('0' <= ch && ch <= '9')) {
    *nr *= 10;
    *nr += ch - '0';
  }
  if (ch == '\r') {
    fgetc(stream);
  }
}

int64_t es[20];
int64_t el = 0;

void pf(int64_t n) {
  int32_t i;
  if ((n & 1) == 0) {
    es[0] = 2;
    ++el;
    while ((n & 1) == 0 && n) {
      n>>=1;
    }
  }
  for(i = 3; i <= n; i += 2) {
    if (n % i == 0) {
      es[el] = i;
      ++el;
      while (n % i == 0 && n) {
        n /= i;
      }
    }
  }
}

int64_t n, k;

int64_t vrf(int64_t nr) {
  int32_t i, j;
  int64_t sumt = 0;
  int64_t prod, k;
  int64_t lim = 1 << el;
  for (i = 1; i < lim; ++i) {
    prod = 1;
    k = 0;
    for (j = 0; j < i; ++j) {
      if ((1<<j) & i) {
        ++k;
        prod *= es[j];
      }
    }
    if (k & 1) {
      sumt += nr / prod;
    } else {
      sumt -= nr / prod;
    }
  }
  return nr - sumt;
}

int64_t bsrc() {
  int64_t cpos;
  int64_t lbound = 0;
  int64_t ubound = INT64_MAX >> 1;
  int64_t answer = lbound;
  while (lbound <= ubound) {
    cpos = (ubound + lbound) / 2;
    if (vrf(cpos) >= k) {
      answer = cpos;
      ubound = cpos - 1;
    } else {
      lbound = cpos + 1;
    }
  }
  return answer;
}

int main(void) {
  {
    FILE *__restrict in = fopen("frac.in", "r");
  
    read_int64_t(in, &n);
    read_int64_t(in, &k);
  
    fclose(in);
  }

  pf(n);

  {
    FILE *__restrict out = fopen("frac.out", "w");

    fprintf(out, "%lu", bsrc());
  
    fclose(out);
  }
  

  return 0;
}