#include <bits/stdc++.h>

using namespace std;
vector <long long> primes;
vector <long long> v;
bitset <10000001> b;
void ciur(long long N)
{
    for(long long i = 2; i * i <= N; i++)
    {
        if(!b[i])
            for(long long j = i * i; j <= N; j+=i)
            {
                b[j] = true;
            }
    }
    for(long long i = 2; i <= N; i++)
        if(!b[i])
            primes.push_back(i);
}
long long solve(long long a,long long b){
     long long c;
        c = b;
        v.clear();
        for(auto x : primes)
        {
            if (1LL * x * x > b)
                continue;

            if(x <= b && b % x == 0)
                v.push_back(x);

            while (b % x == 0)
                b /= x;

        }
        if (b > 1)
            v.push_back(b);
        b = c;
        long long rez = 0;
        for(long long i = 1; i < (1 << v.size()); i++)
        {
            long long nr_bits = 0, p = 1;
            for(long long j = 0; j < v.size(); j++)
            {
                if(i & (1 << j))
                {
                    nr_bits++;
                    p *= v[j];
                }
            }
            if(nr_bits % 2 == 0)
            {
                rez -= (a / p);
            }
            else
            {
                rez += (a / p);
            }
        }
        return a - rez;
}
int main()
{
    ifstream cin("frac.in");
    ofstream cout("frac.out");
    long long m,a,p,r = 0,pas = 1LL << 60;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> a >> p;
    ciur(sqrt(a));

    while(pas){
            if(solve(r + pas,a) < p && r + pas <= N * N)
                r += pas;
        pas /= 2;
    }
    cout << r + 1;
    return 0;
}