#include <bits/stdc++.h>
using namespace std;
vector<long long> v, p;
bool prime[1000010];
long long a, b;
void pre() {
  for (int i = 0; i < 1000000; i++) prime[i] = true;
  for (int i = 2; i < 1000000; i++) {
    if (prime[i]) {
      if (i < 1000)
        for (int j = i * i; j < 1000000; j += i) prime[j] = false;
      p.push_back(i);
    }
  }
  for (int i = 0; i < p.size(); i++) {
    while (a % p[i] == 0) {
      a /= p[i];
      v.push_back(p[i]);
    }
  }
  if (a > 1) v.push_back(a);
}
int main() {
  cin >> a >> b;
  if (a == 1) {
    cout << b << endl;
    return 0;
  }
  if (b == 1 || a == b) {
    cout << "1" << endl;
    return 0;
  }
  long long ans = 0;
  pre();
  while (true) {
    long long amari = 114514114514114514;
    int num = -1;
    for (int i = 0; i < v.size(); i++) {
      if (v[i] == 0) continue;
      if (amari > b % v[i]) {
        amari = b % v[i];
        num = i;
      }
    }
    if (num == -1) {
      ans += b;
      break;
    }
    b /= v[num], ans += amari;
    v[num] = 0;
    if (b == 0) break;
    if (b == 1) {
      ans++;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}
