#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

ifstream fin("zero2.in");
ofstream fout("zero2.out");
#define baza 10
#define MAX 1000000

long long int  n,b,nr;

long long int x,y , i, j;



int main()
{

    for(int kj=1;kj<=10;kj++)
    {
        fin>>n>>b;

        int maxx=0, maxy=0;
        int l=sqrt(b);

        for(i=2;i<=l;i++)
        {
            if(b%i==0)
            {

                x=i;
                y=0;
                while(b%i==0)
                {
                    y++;
                    b/=i;
                }
                l=sqrt(b);
                if(x>maxx)
                {
                    maxx=x;
                    maxy=y;
                }

            }

        }
        if(b>1)
        {
            maxx=b;
            maxy=1;
        }

        for(i=1;i<=n;i++)
        {
            for(j=maxx;j<=i;j*=maxx)
            {
                nr+=i/j;

            }
        }

    nr/=maxy;


        fout<<nr<<"\n";
        nr=0;

    }
    return 0;
}