#include <cstdio>
using namespace std;
FILE *fin=freopen("frac.in","r",stdin);
FILE *fout=freopen("frac.out","w",stdout);

//typedef long long int LL;

long long int n, p, N;
int Div[20], nr;

void Find_Prime_Divisors()
{
    int i;
    if( n % 2 == 0 )
    {
        Div[++nr] = 2;
        while(n % 2 == 0)
            n /= 2;
    }

    for(i = 3; i * i <= n && n > 1; i += 2)
        if(n % i == 0)
        {
            Div[++nr] = i;
            while(n % i == 0)
                n /= i;
        }

    if(n > 1)
        Div[++nr] = n;
}

long long int Pinex(long long int x)
{
    long long int ret = x, cnt, prod, semn;
    long long int k = 1 << nr;

    for( long long int i = 1; i < k; ++i)
    {
        //printf("%lld ", ret);
        cnt = 0, prod = 1;
        for(int j = 0; j < nr; ++j)
            if( i & (1 << j) )
            {
                ++cnt;
                prod *= Div[j + 1];
            }
        if( cnt % 2 == 1 )
            semn = -1;
        else
            semn = +1;
        ret += semn * x / prod;
    }

    return ret;
}

int main()
{
    scanf("%lld %lld", &n, &p);
    N = n;
    Find_Prime_Divisors();

    long long int sol = 0;

    long long int i;

    for(long long int i = 1LL << 61; i > 0; i /= 2)
    {
        if( Pinex(i + sol) <= p && Pinex(i - 1 + sol) < p)
            sol += i;
    }
    printf("%lld", sol);
}