#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;


vector<int> primes, exponents;
vector<int> solution;

void factor( int N) {
	
	for( int i = 2; i * i <= N; ++i) {
		int start = 0;
		while( N % i == 0) 
			start++, N/= i;
		if( start) 
			primes.push_back(i), exponents.push_back(start);
	}
	
	if( N > 1)
		primes.push_back(N), exponents.push_back(1);
}

long long calc_exp( long long N, int prime) {
	
	long long rezult = 0;
	while( N / prime > 0 ) {
		rezult += N /prime;
		N/= prime;
	}
	return rezult;
}

long long find_min_fact( int prime, int exp) {
	
	long long value = 1;
	while( calc_exp( value, prime) < exp)
		value *= 2;
	value /= 2;
	long long rezult = value;
	while(value) {
		if( calc_exp( value + rezult, prime) < exp)
			rezult += value;
		value /= 2;
	}
	return rezult +1 ;
	
}

int main() {
	
	freopen("gfact.in" ,"r", stdin);
	freopen("gfact.out", "w", stdout);
	
	int p, q;
	cin>>p>>q;
	
	factor(p);
	long long optim = 0;
	
	for( size_t i = 0; i < primes.size(); ++i) {
		optim = max( optim, find_min_fact( primes[i], exponents[i] * q));
	}
	
	cout<<optim;
	
	return 0;
}