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

using namespace std;

const int Nmax = 110000;

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

long long N, M;

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

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

    prime[ ++P ] = 2;

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

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

void descomp( long long NR )
{
    for ( int 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 )
{
    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");

    gen();

    f >> N >> M;

    descomp( N );

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

    return 0;
}