#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
map<long long, int> mp;
map<long long, int>::iterator it;
void Factors(long long x) {
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      while (x % i == 0) {
        mp[i]++;
        x /= i;
      }
    }
  }
  if (x != 1) mp[x] = 1;
}
int main() {
  long long a, b;
  scanf("%lld %lld", &a, &b);
  Factors(a);
  long long ans = 0;
  while (b) {
    for (it = mp.begin(); it != mp.end(); it++) {
      while (it->second > 0 && b % it->first == 0) {
        b /= it->first;
        --(it->second);
      }
    }
    long long minn = INF, x = -1;
    for (it = mp.begin(); it != mp.end(); it++) {
      if (it->second > 0 && b % it->first < minn) {
        minn = b % it->first;
        x = it->first;
      }
    }
    if (x == -1) {
      ans += b;
      break;
    }
    ans += minn;
    b -= minn;
  }
  printf("%lld\n", ans);
  return 0;
}
