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

using i64 = long long;

int n, b, e;

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; }

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 << 30; bit > 0; bit = bit / 2)
            if (fun(bit + ans, b) < e)
                ans = ans + bit;
        ans+= 1;
        printf("%lld\n", ans); }
    else {
        int cmd = 1;
        for (int i = 1; i * i <= n; i++)
            if (n % i == 0) {
                cmd = n / i;
                break; }

        for (i64 bit = 1LL << 30; bit > 0; bit = bit / 2)
            if (fun(bit + ans, cmd) < e)
                ans = ans + bit;
        ans+= 1;
        printf("%lld\n", ans); }
    return 0; }