#include <bits/stdc++.h>
using namespace std;
vector<long long> vec;
inline long long gcd(long long a, long long b) {
  return a % b ? gcd(b, a % b) : b;
}
inline long long calc(long long a, long long b) {
  long long Max = 0;
  for (int i = 0; i < vec.size(); ++i) {
    long long t = vec[i];
    if (a % t) continue;
    Max = max(Max, b / t * t);
  }
  return Max;
}
int main() {
  long long a, b, c;
  cin >> a >> b;
  c = a;
  for (long long i = 2; i <= c; ++i) {
    if (i * i > c) break;
    if (c % i == 0) {
      vec.push_back(i);
      while (c % i == 0) c /= i;
    }
  }
  if (c > 1) vec.push_back(c);
  long long ans = 0;
  while (b) {
    long long g = gcd(a, b);
    a /= g, b /= g;
    long long nxt = calc(a, b);
    ans += b - nxt;
    b = nxt;
  }
  cout << ans;
}
