#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int tot;
long long x, y, prime[maxn];
bool is_prime[maxn];
inline void sieve() {
  for (int i = 2; i < maxn; ++i) {
    if (is_prime[i] == 0) {
      prime[tot++] = i;
      for (int j = 2 * i; j < maxn; j += i) is_prime[j] = 1;
    }
  }
}
long long gcd(long long x, long long y) { return !y ? x : gcd(y, x % y); }
long long vec[maxn];
int calc(long long x) {
  int ret = 0;
  for (int i = 0; i < tot; ++i) {
    if (x % prime[i]) continue;
    vec[ret++] = prime[i];
    while (x % prime[i]) x /= prime[i];
  }
  if (x > 1) vec[ret++] = x;
  return ret;
}
long long F1(long long x, long long y) {
  long long ret = 0;
  while (y > 0) {
    if (y % x == 0) return ret + y / x;
    long long _gcd = gcd(x, y);
    x /= _gcd, y /= _gcd;
    int num = calc(x);
    long long tmp = 0x7fffffffffffffff;
    for (int i = 0; i < num; ++i) tmp = min(tmp, y % vec[i]);
    ret += tmp;
    y -= tmp;
  }
  return ret;
}
int main() {
  sieve();
  while (scanf("%I64d%I64d", &x, &y) == 2) cout << F1(x, y) << endl;
  return 0;
}
