#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
#include<cassert>
using namespace std;
#define ull unsigned long long
int main(){
    ios::sync_with_stdio(false);
    ull n, k;
    cin >> n >> k;
    ull re = 1, cnt = 0;
    for (ull i = 1; i <= n; i++){
        ull t = i;
        while (t%k == 0){
            t /= k;
            cnt++;
        }
        re *= t;
        while (re%k == 0){
            re /= k;
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
#define ull unsigned long long
map<ull, ull> prime_cnt_ori;
map<ull, ull> prime_cnt;
ull n, k;
void breakdown_prime(ull k){//将k进行质因数分解，在map中存储每一个质因数
    for (ull i = 2; i <= k; i++){
        while (k%i == 0){
            prime_cnt_ori[i]++;
            k /= i;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    breakdown_prime(k);
    for (ull i = 1; i <= n; i++){
        ull t = i;
        for (map <ull, ull>::iterator iter = prime_cnt_ori.begin(); iter != prime_cnt_ori.end(); iter++){
            while (t % (*iter).first == 0){
                t /= (*iter).first;
                prime_cnt[(*iter).first]++;
            }
        }
    }
    ull mmin = 1e8;
    for (map<ull, ull>::iterator iter = prime_cnt_ori.begin(); iter != prime_cnt_ori.end(); iter++){
        ull t = prime_cnt[(*iter).first] / (*iter).second;
        mmin = min(t, mmin);
    }
    cout << mmin << endl;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
#define ull unsigned long long
struct prime{
    ull number;
    ull cnt;
}prime_cnt_ori[1000000], prime_cnt[1000000];
ull n, k;
ull prime_cnter=0;
void breakdown_prime(ull k){//将k进行质因数分解，在数组中存储每一个质因数
    for (ull i = 2; i <= k; i++){
        if (k%i == 0){
            prime_cnter++;
            prime_cnt_ori[prime_cnter].number = i;
            prime_cnt_ori[prime_cnter].cnt = 0;
            while (k%i == 0){
                prime_cnt_ori[prime_cnter].cnt++;
                k /= i;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    breakdown_prime(k);
    for (ull i = 1; i <= n; i++){
        ull t = i;
        for (int i = 1; i <= prime_cnter;i++){
            while (t % prime_cnt_ori[i].number == 0){
                t /= prime_cnt_ori[i].number;
                prime_cnt[i].cnt++;
            }
        }
    }
    ull mmin = 1e8;
    for (int i = 1; i <= prime_cnter; i++){
        ull t = prime_cnt[i].cnt / prime_cnt_ori[i].cnt;
        mmin = min(t, mmin);
    }
    cout << mmin << endl;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
#define ull unsigned long long
ull prime[1000000], prime_cnt_ori[1000000], prime_cnt[1000000];
ull n, k;
ull prime_cnter = 0;
void breakdown_prime(ull k){//将k进行质因数分解，存储每一个质因数
    for (ull i = 2; i <= k; i++){
        if (k%i == 0){
            prime_cnter++;
            prime[prime_cnter] = i;
            prime_cnt_ori[prime_cnter] = 0;
            while (k%i == 0){
                prime_cnt_ori[prime_cnter]++;
                k /= i;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    breakdown_prime(k);
    for (int i = 1; i <= prime_cnter; i++){
        prime_cnt[i] = 0;
        ull t = prime[i];
        while (n / t){
            prime_cnt[i] += n / t;
            t *= prime[i];
        }
    }
    ull mmin=1e18;
    for (int i = 1; i <= prime_cnter; i++){
        ull t = prime_cnt[i] / prime_cnt_ori[i];
        mmin = min(t, mmin);
    }
    cout << mmin << endl;
    return 0;
}