/*
CodeForces - 837E - Vasya's Function [ 数论 ] | Educational Codeforces Round 26
题意：
f(a, 0) = 0;
f(a, b) = 1 + f(a, b-gcd(a, b));
求 f(a, b) , a,b <= 1e12
分析：
b 每次减 gcd(a, b) 等价于 b/gcd(a,b) 每次减 1
减到什么时候呢，就是 b/gcd(a,b)-k 后 不与 a 互质
可先将 a 质因数分解，b能除就除，不能除就减到最近的a的因子的倍数，即模拟整个过程 由于 a 至多只有 64个因子 （a <= 2^64） ，复杂度挺低
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL INF = 1e18;
const int N = 1e5;
LL a, b;
map<LL, int> mp;
map<LL, int>::iterator it;
void GetFactors(LL x)
{
for (LL 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()
{
scanf("%lld%lld", &a, &b);
GetFactors(a);
LL 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);
}
}
LL mi = INF, x = -1;
for (it = mp.begin(); it != mp.end(); it++)
{
if ((it->second) > 0 && b % (it->first) < mi)
{
mi = b % (it->first);
x = it->first;
}
}
if (x == -1)
{
ans += b; break;
}
ans += mi;
b -= mi;
}
printf("%lld\n", ans);
}