#include <bits/stdc++.h>

using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

bool ciur[400005];
long long n, cnt, primi[200000];
long long rezultat, p, divizori[12];

void eratostene () {
  ciur[0] = ciur[1];

  for (int i = 2; i * i <= 400005; i++) {
    for (int j = i; i * j <= 400005; j++) {
      ciur[i * j] = 1;
    }
  }

  for (int i = 2; i <= 400005; i++) {
    if (!ciur[i]) {
      primi[++cnt] = i;
    }
  }
}

long long submultimi (long long a, long long b) {
  int j = 1;
   int  nr = 0;
    rezultat = 0;
    while (j <= cnt && primi[j] * primi[j] <= b) {
      if (b % primi[j] == 0) {
        divizori[++nr] = primi[j];

        while (b % primi[j] == 0) {
          b /= primi[j];
        }
      }

      j++;
    }

    if (b > 1) {
      divizori[++nr] = b;
    }

    for (int j = 1; j < (1 << nr); j++) {
      int elemente = 0;
      long long p = 1;


      for (int k = 0; k < nr; k++) {
        if (j & (1 << k)) {
          p *= divizori[k + 1];
          elemente++;
        }
      }

      if (elemente % 2) {
        rezultat += (a / p);
      } else {
        rezultat -= (a / p);
      }
    }

    return a - rezultat;
}

int main () {

  fin >> n >> p;

  eratostene();

  long long stanga = 1;
  long long dreapta = ((long long) 1 << 61);
  long long raspuns = ((long long) 1 << 61);

  while (stanga <= dreapta) {
    long long mijloc = (stanga + dreapta) / 2;

    rezultat = submultimi(mijloc, n); // nr numere care sunt prime cu n dar sunt mai mici decat mijloc

    if (rezultat == p) {
      if (mijloc < raspuns) {
        raspuns = mijloc;

        dreapta = mijloc - 1;
      }

    } else if (rezultat < p) {
      stanga = mijloc + 1;
    } else if (rezultat > p) {
      dreapta = mijloc - 1;
    }
  }

  fout << raspuns;

  return 0;
}