#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int prime[100000];
int check[maxn];
long long ys[20][2];
long long gcd(long long a, long long b) { return a == 0 ? b : gcd(b % a, a); }
int main() {
  long long tot = 0;
  memset(check, 0, sizeof(check));
  for (long long i = 2; i < maxn; ++i) {
    if (!check[i]) {
      prime[tot++] = i;
    }
    for (long long j = 0; j < tot; ++j) {
      if (i * prime[j] > maxn) {
        break;
      }
      check[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        break;
      }
    }
  }
  long long x, y;
  while (scanf("%lld%lld", &x, &y) != EOF) {
    long long sum = 0;
    long long z = gcd(x, y);
    x /= z;
    y /= z;
    long long x0 = x;
    int len = 0;
    for (int i = 0; i < tot && prime[i] <= x / 2; i++) {
      if (x0 % prime[i] == 0) {
        ys[len][0] = prime[i];
        ys[len][1] = 0;
        while (x0 % prime[i] == 0) {
          x0 /= prime[i];
          ys[len][1]++;
        }
        len++;
      }
    }
    if (x0 != 1) {
      ys[len][0] = x0;
      ys[len++][1] = 1;
    }
    int j = 0;
    while (x > 1 && y > 1) {
      long long mind = y + 1;
      int d = 0;
      for (int i = 0; i < len; i++) {
        if (ys[i][1] > 0 && mind > y % ys[i][0]) {
          mind = y % ys[i][0];
          d = i;
        }
      }
      sum += mind;
      x /= ys[d][0];
      y /= ys[d][0];
      ys[d][1]--;
    }
    sum += y;
    printf("%lld\n", sum);
  }
  return 0;
}
