#include <bits/stdc++.h>
#define L 1000005
#define S 14
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");

bool ciur[L];
long long primes[S];

void init_ciur(){
  for (int d = 2; d * d < L; d++)
    if (!ciur[d])
      for (int i = d * d; i < L; i += d)
        ciur[i] = true;
}

void prime_decomp(long long x){
  int i = 1;
  for (long long d = 2; d * d <= x; d++)
    if (!ciur[d] && x % d == 0){
      while (x % d == 0)
        x /= d;
      primes[i++] = d;
    }
  if (x > 1)
    primes[i++] = x;
  primes[0] = i - 1;
}

int main(){
  init_ciur();

  long long n, p;
  fin >> n >> p;

  long long st = 1, dr = (1LL << 61), best = 1;
  while (st <= dr){
    long long mid = (st + dr) / 2;

    long long ans = 0;
    prime_decomp(n);
    for (int mask = 1; mask < (1 << primes[0]); mask++){
      long long x = 1;
      int cnt = 0;
      for (int bit = 0; bit < primes[0]; bit++)
        if ((1 << bit) & mask){
          x *= primes[bit + 1];
          cnt++;
        }
      ans += 1LL * (cnt % 2 * 2 - 1) * (mid / x);
    }
    ans = mid - ans;

    if (ans < p)
      st = mid + 1;
    else{
      best = mid;
      dr = mid - 1;
    }
  }

  fout << best << "\n";
  return 0;
}