#include <bits/stdc++.h>
using namespace std;
vector<long long> p, c;
int sp[1000010], sz = 0;
vector<long long> factorise(int i) {
  vector<long long> ret;
  if (i == p.size()) {
    ret.push_back(1);
    return ret;
  }
  ret = factorise(i + 1);
  long long n = ret.size();
  long long pr = 1;
  for (int j = 0; j < c[i]; ++j) {
    pr *= p[i];
    for (int u = 0; u < n; ++u) {
      ret.push_back(ret[u] * pr);
    }
  }
  return ret;
}
vector<long long> factors(long long n) {
  for (long long i = 2; i < 1000010; ++i) {
    if (sp[i] != i || n % i != 0) continue;
    p.push_back(i);
    n /= i;
    long long cnt = 1;
    while (n % i == 0) {
      ++cnt;
      n /= i;
    }
    c.push_back(cnt);
  }
  if (n != 1) {
    p.push_back(n);
    c.push_back(1);
  }
  return factorise(0);
}
void sieve() {
  for (int i = 1; i < 1000010; ++i) {
    if (i & 1)
      sp[i] = i;
    else
      sp[i] = 2;
  }
  int sq = sqrt(1000010);
  for (long long i = 3; i <= sq; i += 2) {
    if (sp[i] != i) continue;
    for (long long j = i * i; j < 1000010; j += i) {
      if (sp[j] == j) sp[j] = i;
    }
  }
}
long long gcd(long long a, long long b) {
  if (a < b) swap(a, b);
  return ((b == 0) ? a : gcd(b, a % b));
}
int main() {
  sieve();
  long long a, b;
  scanf("%lld %lld", &a, &b);
  vector<long long> f = factors(a);
  sort(f.begin(), f.end());
  long long g = gcd(a, b), ans = 0;
  while (b != 0) {
    long long mn = b, fact = 1;
    for (int i = 1; i < f.size(); ++i) {
      long long t = g * f[i];
      if (t > b || t > a) break;
      if (a % t) continue;
      if (b % t <= mn) {
        mn = b % t;
        fact = f[i];
      }
    }
    ans += mn / g;
    b -= mn;
    g = g * fact;
  }
  printf("%lld\n", ans);
  return 0;
}
