#include <bits/stdc++.h>
using namespace std;
long long p[1010], cnt;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long work(long long a, long long b) {
  if (!b) return 0;
  long long d = gcd(a, b);
  a /= d;
  b /= d;
  long long A = a;
  long long minn = b;
  for (long long i = 2; i * i <= A; ++i) {
    if (A % i) continue;
    minn = min(minn, b % i);
    while (A % i == 0) A /= i;
  }
  if (A > 1) minn = min(minn, b % A);
  return minn + work(a, b - minn);
}
int main() {
  long long a, b;
  scanf("%I64d%I64d", &a, &b);
  printf("%I64d", work(a, b));
  return 0;
}
