#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 ( 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 prod = 1;

        for ( int j = 0; j < NRDIV; ++j )
                if ( i & ( 1 << j ) )
                {
                    prod *= DIV[j];
                    nrb++;
                }

        if ( nrb % 2 )
                solution += val / prod;
        else
                solution -= val / prod;
    }

    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;
}