#include <bits/stdc++.h>
using namespace std;
long long pwr(long long base, long long p, long long mod = (1000000007LL)) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long calc(long long a, long long b) {
  if (b == 0) return 0;
  if (a == b) return 1;
  long long g = gcd(a, b), rem = a / g;
  long long steps = 1e16, nxt = -1;
  for (long long i = 2; i * i <= rem; i++)
    if (rem % i == 0) {
      while (rem % i == 0) rem /= i;
      long long temp = (b - (b / (i * g)) * (i * g)) / g;
      if (temp < steps) {
        steps = temp;
        nxt = (b / (i * g)) * (i * g);
      }
    }
  if (rem > 1) {
    long long temp = (b - (b / (rem * g)) * (rem * g)) / g;
    if (temp < steps) {
      steps = temp;
      nxt = (b / (rem * g)) * (rem * g);
    }
  }
  if (nxt == -1) return b / g;
  return steps + calc(a, nxt);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long a, b;
  cin >> a >> b;
  cout << calc(a, b);
  return 0;
}
