Untitled

#include <bits/stdc++.h>

using namespace std;

#define Chris "test"
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORD(i, a, b) for(int i = (a); i <= (b); ++i)
#define REP(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >= (b); --i)
#define FORE(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define All(v) (v).begin(), (v).end()
#define rAll(v) (v).rbegin(), (v).rend()
#define MARK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
#define el "\n"
#define Chris_ signed main()
#define faster ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define file(Chris) if(fopen(Chris".inp", "r")){freopen(Chris".inp", "r", stdin);freopen(Chris".out", "w", stdout);}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<ull> vii;
typedef set<int> sii;
typedef map<ull, ull> mii;
typedef stack<int> sti;
typedef deque<int> dqi;
typedef queue<int> quei;
typedef unordered_map<int, int> umii;

const int mod = (int) 1e5;
const int INF = (int) 1e9;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ull n;
int k;

vii factors(int k)
{
    vii res;
    ull i = 2;
    while(i <= sqrt(k))
    {
        if(k % i == 0)
        {
            k /= i;
            res.pb(i);
        }
        else
        {
            ++i;
        }
    }
    if(k > 1)
    {
        res.pb(k);
    }
    return res;
}

ull tinh(ull n, int k)
{
    vii f = factors(k);
    mii tmp;
    for(ull i : f)
    {
        if(tmp.find(i) == tmp.end())
        {
            ull temp = n, kq = 0;
            while(temp)
            {
                temp /= i;
                kq += temp;
            }
            tmp[i] = kq;
        }
    }
    ull min_tinh = ULLONG_MAX;
    for(ull i : f)
    {
        min_tinh = min(min_tinh, tmp[i] / count(All(f), i));
    }
    return min_tinh;
}

void solve(ull n, int k)
{
    cout << tinh(n, k);
}

Chris_
{
    faster
    file(Chris)

    cin >> n >> k;
    solve(n, k);

    return 0;
}