#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1111;
const int INF = 0x7f7f7f7f;
int cases;
template <class T>
T gcd(T a, T b) {
  if (!a) return 1;
  if (!b) return a;
  if (a < 0) a = -a;
  for (T t; b; t = a % b, a = b, b = t)
    ;
  return a;
}
vector<long long> fact(long long x) {
  vector<long long> a;
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      a.emplace_back(i);
      while (x % i == 0) x /= i;
    }
  }
  if (x != 1) a.emplace_back(x);
  return a;
}
int main() {
  long long x, y, ans = 0;
  cin >> x >> y;
  while (y > 0) {
    auto g = gcd(x, y);
    x /= g, y /= g;
    auto v = fact(x);
    long long p = 0;
    for (const auto& f : v) {
      p = max(p, (y - 1) / f * f);
    }
    ans += y - p;
    y = p;
  }
  cout << ans << '\n';
}
