#include<bits/stdc++.h>
#define ll int
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
ll kq(ll n, ll d) {
    ll s=0;
    for(int i=n;i>0;i/=d)
        s+=i/d;
    return s;
}
ll n, p;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>p;
    ll s=INT_MAX;
    for(int i=2;i<=p;i++)
    {
        if(p%i==0)
        {
            int d=0;
            while(p%i==0)
             {
                p/=i;
                d++;
            }
            s=min(s,kq(n,i)/d);
        }
    }
    cout<<s;
    return 0;
}
/*

*   *  *   *    *     *   *       *****    *     ****         ***    ***   ****   *****
**  *  *   *   * *    **  *         *     * *    *   *       *   *  *   *  *   *  *
* * *  *   *  *   *   * * *         *    *   *   *   *       *      *   *  *   *  *
*  **  *****  *****   *  **         *    *****   ****        *      *   *  *   *  ****
*   *  *   *  *   *   *   *         *    *   *   *           *      *   *  *   *  *
*   *  *   *  *   *   *   *         *    *   *   *           *   *  *   *  *   *  *
*   *  *   *  *   *   *   *         *    *   *   *            ***    ***   ****   *****

*/