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

using namespace std;

int DIV[100], NRDIV;

long long N, M;

void descomp( long long NR )
{
    for ( long long i = 2; i * i <= NR && NR > 1; ++i )
    {
        if ( NR % i == 0 )
        {
            DIV[ NRDIV++ ] = i;

            while ( NR % i == 0 ) NR /= i;
        }
    }

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

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

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

        for ( int 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 )
{
    if ( st > dr )
            return st;

    long long mid = st + ( dr - st ) / 2;
    long long numar = mid - PIE( mid );

    if ( numar >= M )
            return bsearch( st, mid - 1 );
    else
            return bsearch( mid + 1, dr );
}

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

    f >> N >> M;

    descomp( N );

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

    return 0;
}