#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>
#include <limits.h>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

using namespace std;
ifstream in("frac.in");
ofstream out("frac.out");

using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 5e6 + 5;
const int inf = 1e9 + 5;
const int mod = 100003;
using zint = int;

ll N,P;
ll primes[1000];

ll getPhi(ll N,ll B);

int main() {
    in>>N>>P;

    for (int i=1;i <= 20;++i) {
        pv(i);pv(getPhi(i,N));
        pn;
    }

    ll pos = 0,pw = 1, lim = 1ull<<60;
    for(;pw <= lim;pw <<= 1) ;
    pw >>= 1;

    while (pw) {
        if (getPhi(pos+pw,N) < P) {
            pos += pw;
        }

        pw >>= 1;
    }

    out<<pos+1<<'\n';

    in.close();out.close();
    return 0;
}

ll getPhi(ll N,ll B) {
    ll nrPrimes = 0;

    ll aux = B;
    for (ll i=2;i*i <= aux;++i) {
        if (aux % i != 0) {
            continue;
        }

        while (aux % i == 0) {
            aux /= i;
        }

        primes[++nrPrimes] = i;
    }
    if (aux != 1) {
        primes[++nrPrimes] = aux;
    }

    /*
    pv(B),pn;
    for (int i=1;i <= nrPrimes;++i) {
        pv(primes[i]);
    }
    pn;
    //*/

    ll lim = 1<<nrPrimes, total = 0;
    for (ll mask = 1;mask < lim;++mask) {

        ll prod = 1,nr = 0;
        for (ll i=1;i <= nrPrimes;++i) {
            if (((1<<(i-1)) & mask) != 0) {
                prod *= primes[i];
                ++nr;
            }
        }

        //pv(prod);
        ll card = (nr % 2 == 1) ? N/prod : -N/prod;
        total += card;
    }
    //pn;

    return N - total;
}