#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <vector>
#define MAX (1LL << 62)
#include <math.h>

using namespace std;

vector <long long> diviz;
vector <long long> solut;
long long n;
long long p;
long long sum = 0;
long long prod = 1;
void prime(long long x,long long last)
{

    for (long val=solut[last]+1;val<=diviz.size();val++)
    {
        solut.push_back(last);
        prod *= diviz[last-1];
        sum += ((int)pow(-1,last-1) * x / prod);
        prime(x,last+1);
        prod /= diviz[last-1];
    }


}

int main()
{
    FILE *input = fopen("frac.in","r");
    FILE *output = fopen("frac.out","w");
    fscanf(input,"%lld",&n);
    fscanf(input,"%lld",&p);

    long long div = 1;
    long long cpy = n;

    while (cpy != 1)
    {
        div++;
        if (cpy % div == 0)
        {
            diviz.push_back(div);
            while (cpy % div == 0)
            {
                cpy /= div;
            }
        }
    }
    long long st = 0;
    long long dr = 26;
    long long sol = 0;
    while (st <= dr)
    {
        long long m = (st + dr ) / 2;
        solut.push_back(0);

        sum = 0;
        prod = 1;
        prime(m,1);
        sum = m - sum - 1;
        if (sum >= p)
        {
            sol = m;
            dr = m-1;
        }
        else
        {
            st = m+1;
        }
    }
    fprintf(output,"%lld",sol);
    fclose(input);
    fclose(output);
    return 0;
}