#include <fstream>
#include <vector>
using namespace std;

ifstream cin ("frac.in");
ofstream cout ("frac.out");

long long Divizibile (long long limita , vector <long long> factori)
{
    long long divizori = 0;
    for (int masca = 1 , limita_masca = (1 << factori.size()) ; masca < limita_masca ; masca++)
    {
        int lungime = 0;
        long long impartitor = 1;
        for (int indice = 0 , putere = 1 ; putere <= masca ; indice++ , putere <<= 1)
            if (masca & putere) impartitor *= factori[indice] , lungime++;
        
        if (lungime & 1) divizori += limita / impartitor;
        else divizori -= limita / impartitor;
    }

    return divizori;
}

int main ()
{
    long long numitor , cautat;
    cin >> numitor >> cautat;

    long long copie = numitor;
    vector <long long> factori;
    for (long long factor = 2 ; factor * factor <= copie ; factor++)
        if (copie % factor == 0) {
            factori.push_back(factor);
            while (copie % factor == 0)
                copie /= factor;
        }

    if (copie > 1) factori.push_back(copie);
    long long stanga = 1 , dreapta = (1LL << 61) , divizibile = 1;
    while (stanga <= dreapta)
    {
        long long mijloc = (stanga + dreapta) >> 1;
        if (mijloc - Divizibile(mijloc , factori) >= cautat)
            divizibile = mijloc , dreapta = mijloc - 1;
        else
            stanga = mijloc + 1;
    }

    cout << divizibile;
    cout.close(); cin.close();
    return 0;
}