#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

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

#define nmax 1000
#define sqrtN 2000000
#define ll long long
#define inf (1LL << 45)

int factor[nmax];
bool viz[sqrtN];
int prim[sqrtN];
ll n, P;

void citeste(){

	f >> n >> P;

}

bool check(ll X){

    //acum trebuie sa aflu cate numere sunt mai mici ca X si neprime cu n;

    ll cnt = X;
    for(int conf=1; conf<(1<<factor[0]); ++conf){//iau fiecare submultime a descompunerii in factori primi
        ll nr = 0;
        ll prod = 1;
        for(int j=0; j<factor[0]; ++j){
            if ( (conf & (1<<j)) != 0 ){//daca am 1 pe j in conf
                prod = 1LL * prod * 1LL*factor[j+1];
                ++nr;
            }
        }
        if (nr & 1 !=0 ){
            nr = -1;
        }else nr = 1;
        cnt = cnt + 1LL * nr * X / prod;
    }


    if (cnt >= P) return 1;
    return 0;

}

void ciur(){

    viz[1] = 1;
    for(int i=2; i<sqrtN; ++i){
        if (viz[i] == 0){
            prim[ ++prim[0] ] = i;
            for(int j=i*2; j<sqrtN; j+=i){
                viz[j] = 1;
            }
        }
    }

}

void descompune_n(){

    ll cpy = n;
    int j = 1;
    while(cpy > 1 && j <= prim[0]){
        if (cpy %prim[j] == 0){
            while(cpy%prim[j] == 0){
                cpy = cpy / prim[j];
            }
            factor[ ++factor[0] ] = prim[j];
        }
        ++j;
    }
    if(cpy > 1){
        factor[ ++factor[0] ] = cpy;
    }

}

void rezolva(){

    //trebuie sa aflu a P-a fractie ireductibila(numitorul fiind n)
    //practic imi cere al P-lea numator adica al P-lea numar prim cu n;
    //caut binar raspunsul adica imi fixez un numar si vad cate numare mai mici ca el exista si sa fie prime cu n;
    //=> pentru un X fixat aflu cate numere sunt mai mici ca el si neprime cu n; => aplic principiul includeri/excluderii

    ciur();
    descompune_n();

    check(n);

    ll st = 0;
    ll dr = inf;
    while(dr - st > 1){
        ll mij = (st + dr) / 2;
        if (check(mij) == 1){
            dr = mij;
        }else st = mij;
    }

    g << dr << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}