#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
template <class T>
T gcd(T a, T b) {
  if (!b) return a;
  return gcd(b, a % b);
}
const int maxn = 1e6 + 100;
int tb[maxn], prm[maxn], p_len, vis[120];
long long p[120];
void init() {
  memset(tb, 0, sizeof(tb));
  p_len = 0;
  for (int i = 2; i < maxn; i++) {
    if (tb[i] == 0) {
      prm[p_len++] = i;
    }
    for (int j = 0; j < p_len; j++) {
      if (prm[j] * i >= maxn) break;
      tb[prm[j] * i] = 1;
      if (i % prm[j] == 0) break;
    }
  }
}
int main() {
  init();
  long long x, y;
  cin >> x >> y;
  int cnt = 0;
  long long tmp = x;
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i < p_len; i++) {
    while (tmp % prm[i] == 0) {
      p[cnt++] = prm[i];
      tmp /= prm[i];
    }
  }
  if (tmp > 1) p[cnt++] = tmp;
  long long ans = 0;
  long long dis[120];
  while (1) {
    if (y == 0) break;
    if (x == 1) {
      ans += y;
      break;
    }
    long long mn = INF;
    for (int i = 0; i < cnt; i++) {
      if (vis[i]) continue;
      dis[i] = y - (y / p[i]) * p[i];
      mn = min(mn, dis[i]);
    }
    ans += mn;
    y -= mn;
    for (int i = 0; i < cnt; i++) {
      if (vis[i]) continue;
      if (dis[i] == mn && y % p[i] == 0) {
        x /= p[i];
        y /= p[i];
        vis[i] = 1;
      }
    }
  }
  cout << ans << endl;
  return 0;
}
