/**
 *   author: malviyanshiv
 *   created: 10 February 2019  20:15:50
**/

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for(int i = a; i < b; i++)
#define RREP(i, a, b) for(int i = a-1; i >= b; i--)

#define FORE(a) for(auto ele : a )
#define PB push_back
#define MP make_pair
#define MOD 1000000007
#define INF 0x7fffffff
#define LINF 2000000000000000007
#define F first
#define S second
#define TC int t; cin >> t; while(t--)
#define ALL(a) begin(a), end(a)
#define MAX 1000005

typedef long long ll;
typedef pair< int, int > PII;


void optimizeIO(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
}

int main(){
    optimizeIO();

    ll n,b;
    cin >> n >> b;
    vector<bool> prime(MAX, 1);
    bool is_prime = true;
    for(ll i = 2; i < MAX; i++){
        if( prime[i] == 1 ){
            if( is_prime && b%i == 0 && i != b)
                is_prime = false;
            for(ll j = 2*i; j < MAX; j+=i)
                prime[j] = 0;
        }
    }
    if( is_prime ){
        ll pw = 0;
        ll j = b;
        ll temp=1;
        ll mmm = log2(n)/log2(b);
        while( temp <= mmm ){
            pw += (n/j);
            j = j*b;
            temp++;
        }
        cout << (pw) << endl;
        return 0;
    }
    ll res = LINF;
    
    for(ll i = 2; i < MAX; i++){
        if( prime[i] && b%i == 0 ){
            ll pw = 0;
            ll j = i;
            ll temp = 1;
            ll mmm = log2(n)/log2(i);
            while( temp <= mmm ){
                pw += (n/j);
                j = j*i;
                temp++;
            }
            ll tb = b;
            ll cnt = 0;
            while( tb%i == 0 )
                tb = tb/i, cnt++;
            res = min( res, (ll)(pw/cnt));
        }
    }
    cout << res << endl;
    
    return 0;
}