#include <iostream>
#include <fstream>
#include <bitset>

using namespace std;

const long long Nmax = 110000;

bitset <Nmax> ciur;
long long prime[Nmax], P;
long long DIV[Nmax], NRDIV;

long long N, M;

void gen()
{
    for ( long long i = 2; i < Nmax; ++i )
            ciur[i] = 1;

    for ( long long i = 4; i < Nmax; i += 2 )
            ciur[i] = 0;

    prime[ ++P ] = 2;

    for ( long long i = 3; i < Nmax; i += 2 )
            if ( ciur[i] == 0 )
            {
                prime[ ++P ] = i;

                for ( long long j = 3 * i; j < Nmax; j += 2 * i )
                        ciur[j] = 0;
            }
}

void descomp( long long NR )
{
    for ( long long i = 1; i <= P && 1LL * prime[i] * prime[i] <= NR; ++i )
    {
        if ( NR % prime[i] ) continue;

        DIV[ NRDIV++ ] = prime[i];

        while ( NR % prime[i] == 0 ) NR /= prime[i];
    }

    if ( NR > 1 )
    {
        DIV[ NRDIV++ ] = NR;
    }
}

long long PIE( long long val )
{
    long long lim = 1 << NRDIV;
    long long solution = 0;

    for ( long long i = 1; i < lim; ++i )
    {
        long long nrb = 0;
        long long cont = val;

        for ( long long j = 0; j < NRDIV; ++j )
                if ( i & ( 1 << j ) )
                {
                    cont /= DIV[j];
                    nrb++;
                }

        if ( nrb % 2 )
                solution += cont;
        else
                solution -= cont;
    }

    return solution;
}

long long bsearch( long long st, long long dr, long long pos )
{
    long long mid;
    long long sol = -1;

    while ( st <= dr )
    {
        mid = st + ( dr - st ) / 2;

        if ( mid - PIE( mid ) >= pos )
        {
            sol = mid;
            dr = mid - 1;
        }
        else
        {
            st = mid + 1;
        }
    }

    return sol;
}

int main()
{
    ifstream f("frac.in");
    ofstream g("frac.out");

    gen();

    f >> N >> M;

    descomp( N );

    g << bsearch( 2LL, ( 1LL << 61 ), M );

    return 0;
}