#include<stdio.h>

FILE*f=fopen("frac.in","r");
FILE*g=fopen("frac.out","w");

int nrf,F[50]; 
long long N,P;

inline void descompunere () {
	long long n = N;
	
	for ( int i = 2 ; n > 1 && 1LL * i * i <= n ; ++i ){
		
		if ( !(n % i) ){
			++nrf; F[nrf] = i;
			
			while ( !(n % i) ){
				n /= i;
			}
		}
	}
	
	if ( n > 1 ){
		++nrf; F[nrf] = n;
	}
	
}

long long pinex( long long A ){
	int nr; long long prod; long long R = 0;
	
	for ( int i = 1 ; i < ( 1 << nrf ) ; ++i ){
		prod = 1; nr = 0;
		
		for ( int j = 0 ; j < nrf ; ++j ){
			
			if ( i & ( 1 << j ) ){
				prod = prod * F[j+1];
				++nr;
			}
			
		}
		
		if ( nr & 1 ){
			R += A / prod;
		}
		else
			R -= A / prod;
	}
	
	return (A - R + 1LL);
}

long long cb () {
	
	long long x,m,p,u;
	p = 1; u = 1LL << 61;
	
	while ( p <= u ){
		
		m = p + ( u - p ) / 2;
		
		x = pinex(m);
		
		if ( x > P )
			u = m - 1;
		else
			p = m + 1;
		
	}
	
	return p;
}

int main () {
	
	fscanf(f,"%lld %lld",&N,&P);
	
	descompunere();
	
	fprintf( g,"%lld\n",cb() );
	
	fclose(f);
	fclose(g);
	
	return 0;
}