#include<cstdio>
    #include<iostream>
    #include<vector>
    using namespace std;
    #define pb push_back
    #define LL long long
    long long  N , P , rez , nrp ;
    vector<int> d;

     bool prim(int n);
     void solve(LL A);

    int main()
    {
        freopen("frac.in" , "r" , stdin );
        freopen("frac.out" , "w" , stdout );
        cin>>N>>P;
        for(int i = 2 ; i*i <= N ; ++i )
        {
            if(N%i==0)d.pb(i);
            while(N%i == 0)N/=i;
        }
        if(N > 1)d.pb(N);
        LL ls = 1 , ld = (1ll<<61) + 1 , mid;
        while(ls <= ld )
        {
            mid = (ls+ld)/2;
            solve(mid);
            if( nrp >= P )
            {
                rez = mid;
                ld = mid-1;
            }
            else ls = mid+1;
        }
        cout<<rez;
        return 0;
    }

    void solve(LL A)
    {
        nrp = 0;
        int k = (int)d.size();
        for(LL i = 1 ; i < (1ll << k) ; ++i )
        {
            LL prod = 1;
            LL nr = 0;
            for(int j = 0 ; j < k ; ++j )
                if(i&(1<<j))
                    prod*=d[j],nr++;
            if(nr%2)nrp += A/prod;
            else nrp -= A/prod;
        }
        nrp = A-nrp;
    }

    bool prim(int n)
    {
        if(n%2==0)return 0;
        for(int i = 3 ; i*i <= n ; i+=3)
            if(n%i==0)return 0;
        return 1;
    }