#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long f(long long a, long long b) {
  if (!b) return b;
  long long g = gcd(a, b);
  a /= g, b /= g;
  long long ne = a, mn = b;
  for (long long i = 2; i * i <= a; i++)
    if (a % i == 0) {
      mn = min(mn, b % i);
      while (a % i == 0) a /= i;
    }
  if (a != 1) mn = min(mn, b % a);
  return mn + f(ne, b - mn);
}
int main() {
  long long a, b;
  cin >> a >> b;
  cout << f(a, b) << endl;
}
