#include <fstream>

using namespace std;

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

/*
    Referinta la problema PINEX - gasirea numarului de numere prime mai mici ca B si prime cu A
    De fapt, noi gaseam toate numarele MAI MICI ca B si NEPRIME cu A, ca apoi sa le scadem din B si obtineam
    numarul de numere PRIME cu A

    semnficatie a cifrelor in ACEASTA problema
    A - numar citit si de referinta
    b - indicele numarului cautat - asta este, de fapt, numarul de numere MAI MICI ca P1 si prime cu A pe care trebuie sa il aiba un numar pentru a fi raspunsul
    p1 - cel  mai mic numar cu b numere mai mici ca p1 si prime cu A



    Cu cautare binara pe biti, ideea este sa gasim CEL MAI MARE numar
    care are b - 1 numere prime cu A.
    Astfel, urmatorul numar va fi cel mai mic numar cu b numere prime cu A.

    Ideea este sa gasim cautam binar acest numar. Crestem P1 ( numarul efectiv) doar cand
    numarul de numere mai mici ca el si prime cu A este mai mic ca si b.

    Ca sa gasim cate numere mai MICI ca P si prime cu A sunt, folosim PINEX.

*/

long long p[55],a,b,x,y,i,u,m,pr,j, d;

void rez()
{

    long long power = (long long) 1 << 61;
    long long p1 = 0;

    for( ; power ; power >>= 1) // cautam binar numarul P
    {

        long long y = p1 + power;

        // y reprezinta numarul de numere mai mici ca P1 + POWER si prime cu A

        for (i = 1 ; i < (1 << d); i++) // pinex
        {
            for (pr = 1, j = 0 ; j <= d; j++)
                if ((i & (1 << j)))
                    pr *= -p[j+1];

            y += (p1 + power) / pr;
        }



        if(y < b) // verificam daca crestem
            p1 += power;

    }


    cout << p1 + 1; // afisam numarul urmator
}

int main()
{
    cin >> a >> b;

    for(int i = 2 ; i * i <= a ; i++)
        if(!(a % i))
            for(p[++d] = i ; !(a % i) ; a /= i);

    if(a > 1)
        p[++d] = a;

    rez();

    return 0;
}