#include <bits/stdc++.h>
using namespace std;
const long long LLINF = LLONG_MAX;
const int INF = INT_MAX;
const int MAXN = 2e2 + 10;
const int mod = 1e9 + 7;
const int MAXPRIME = 3162300;
bool notp[MAXPRIME];
vector<int> p;
long long a, b;
long long ans;
void sieve() {
  for (long long i = 2; i < MAXPRIME; i++) {
    while (notp[i]) i++;
    p.push_back(i);
    for (long long j = i + i; j < MAXPRIME; j += i) notp[j] = true;
  }
}
bool prime(long long a) {
  for (int i = 0; i < p.size() && 1ll * p[i] * p[i] <= a; i++)
    if (a % p[i] == 0) return false;
  return true;
}
long long gcd(long long a, long long b) {
  return (b == 0ll) ? a : gcd(b, a % b);
}
long long solve(long long a, long long b) {
  if (b == 0ll) return 0ll;
  if (prime(a)) {
    if (a == b) return 1ll;
    if (a > b) return b;
    return b % a + b / a;
  }
  long long ans = 0ll;
  long long div = gcd(a, b);
  while (div == 1) ans++, b--, div = gcd(a, b);
  a /= div, b /= div;
  return ans + solve(a, b);
}
int main() {
  scanf("%I64d%I64d", &a, &b);
  sieve();
  printf("%I64d\n", solve(a, b));
  return 0;
}
