#include <bits/stdc++.h>
using namespace std;
vector<long long> p(0);
vector<int> freq(0);
long long x, y;
void init() {
  long long t = x;
  for (int i = 2; i <= sqrt(t); i++) {
    int f = 0;
    while (t % i == 0) {
      t /= i;
      f++;
    }
    if (f) {
      p.push_back(i);
      freq.push_back(f);
    }
  }
  if (t != 1) {
    p.push_back(t);
    freq.push_back(1);
  }
}
int main() {
  cin >> x >> y;
  init();
  long long g = 1;
  long long ans = 0;
  while (y != 0) {
    long long min = y / g;
    long long minp = -1;
    for (int i = 0; i < p.size(); i++) {
      if (freq[i]) {
        if ((y - (y / p[i] / g) * p[i] * g) / g < min) {
          min = (y - (y / p[i] / g) * p[i] * g) / g;
          minp = i;
        }
      }
    }
    ans += min;
    y -= g * min;
    if (minp != -1) {
      freq[minp]--;
      g *= p[minp];
    }
  }
  cout << ans << endl;
}
