#include <fstream>

using namespace std;

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

long long n, p, cn, a[50], k, total, last;

bool prime_intre_ele(long long d, long long i)  {
  long long r = d % i;
  while (r)  {
    d = i;
    i = r;
    r = d % i;
  }
  return (i == 1);
}

void pinex(long long prod, int last, int nr)  {
  if (nr)  {
    if (nr % 2 == 0)
      total -= p / prod;
    else
      total += p / prod;
  }
  for (int i = last + 1; i <= k; ++i)
    pinex(prod * a[i], i, nr + 1);
}

int main()  {
  fin >> n >> p;
  cn = n;
  if (cn % 2 == 0)  {
    a[++k] = 2;
    while (cn % 2 == 0)
      cn /= 2;
  }
  for (long long d = 3; d * d <= cn; d += 2)  {
    if (cn % d == 0)  {
      a[++k] = d;
      while (cn % d == 0)
        cn /= d;
    }
  }
  if (cn > 1)
    a[++k] = cn;
  pinex(1, 0, 0);
  p += total;
  while (last != total)  {
    last = total;
    total = 0;
    pinex(1, 0, 0);
    p += total - last;
  }
  while (!prime_intre_ele(p, n))
    ++p;
  fout << p;
}