#include <iostream>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

const long long INFMAX = 1LL << 61 ;
const int N = 10 ;
long long primes [ N ] , prCr ;
long long sgn[ 1<<N ] , prod [ 1<<N ] ;

void PreCalc ( ){
    static int i , j ,power  ;


    for( i = 1 ; i < (1<<prCr) ; i++ ){
        prod [ i ] = 1 ;
        power = 0 ;
        for ( j = 0 ; j < prCr ; j++ ){
            if ( ( 1 << j ) & i ){
                power ++ ;
                prod [ i ] = prod [ i ] * 1LL * primes [ j + 1 ] ;
            }
        }
        if ( power % 2 == 0 ){
            power = 1 ;
        }else{
            power = -1 ;
        }
        sgn [ i ] = power ;
    }

}

long long FindNoDiv ( long long x ){
    static long long sum , i;

    sum = x ;

    for ( i = 1 ; i < ( 1 << prCr ) ; i ++ ){
        sum = sum + x * sgn [ i ] / prod [ i ] ;
    }

    return sum ;
}


long long BnrSrch ( int x ){
    static long long st , dr , mid ,val ;

    st = 0 ;
    dr = INFMAX ;

    while ( st < dr ){


        mid = st - ( st - dr ) /2 ;
        if ( mid == 16 ){
            printf("1 ");
        }
        val = FindNoDiv( mid );

        if ( val > x ){
            dr = mid - 1 ;
        }else if ( val < x ){
            st = mid + 1 ;
        }else {
            dr = mid ;
        }

    }
    return dr ;
}


int main(){
    long long n , p ;
    long long i ;

    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);

    scanf("%lld%lld",&n,&p);

    for ( i = 2 ; i * i <= n ; i ++ ){
        if ( n % i == 0 ){
            while ( n % i == 0 ){
                n/=i ;
            }
            primes [ ++prCr ] = i ;
        }
    }
    if ( n != 1 ){
        primes [ ++prCr ] = n ;
    }

    PreCalc ();

    printf("%lld", BnrSrch ( p ) );


    return 0;
}