#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int n, b, e, nc = 0;

int f[200], p[200];

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

void des(int n){
    int x = 2;
    while(x * x <= n && n > 1) {
        if (n % x == 0)
            f[++nc] = x;
        while(n % x == 0) {
            p[nc]++;
            n = n / x; }
        x++; }
    if (n > 1){
        f[++nc] = n;
        p[nc] = 1; } }

i64 fun(i64 x, int n) {
    i64 ans = 0;
    while (x / n > 0) {
        ans = ans + x / n;
        x = x / n; }
    return ans; }



int main() {
    freopen("gfact.in", "r", stdin);
    freopen("gfact.out", "w", stdout);
    i64  ans = 0;
    scanf("%d %d", &b, &e);
    if (prim(b)) {
        for (i64 bit = 1LL << 60; bit > 0; bit = bit / 2)
            if (fun(bit + ans, b) < e)
                ans = ans + bit;
        ans+= 1;
        printf("%lld\n", ans); }
    else {
        des(b);
        int cmd = 1;
        long long man = 0;
        for (int i = 1; i <= nc; i++) {
            ans = 0;
            cmd = p[i] * e;
            for (i64 bit = 1LL << 60; bit > 0; bit = bit / 2)
                if (fun(bit + ans, f[i]) < cmd)
                    ans = ans + bit;
            ans+= 1;
            if (ans > man)
                man = ans ; }
        printf("%d", man); }
    return 0; }