import java.util.Scanner;

/**
 * @author:     86182
 * @description: 求n！在m 进制下末尾0的个数
 * @date:    2021/4/9 16:37
 */
public class ZeroNum {

    /**
     * ind[]:存m有几个质数，例如10的质数是2一个，5一个
     */
    static int[] ind = new  int[108];
    /**
     * cnt[]:存q * k
     */
    static int[] cnt = new  int[108];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        int[] prime = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

        int tmp = m;
        for (int i = 1; i <= 25; i++) {
            while (tmp % prime[i] == 0){
                ind[prime[i]]++;
                tmp /= prime[i];
            }
        }
        for (int i = 1; i <= 25; i++) {
            if(ind[prime[i]] != 0){
                cnt[prime[i]] = getcnt(prime[i], n);
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= 25; i++) {
            if(ind[prime[i]] != 0){
                ans = Math.min(ans, cnt[prime[i]]/ind[prime[i]]);
            }
        }
        System.out.println(ans);
    }


    /**
     * n的阶乘分解质因数后有几个x
     * @param n
     * @param x
     * @return n!中x的个数
     */
    public static int getcnt(int n, int x){
        int res = 0;
        while (x != 0){
            res += x / n;
            x /= n;
        }
        return res;
    }


    /**
     * 求n!
     * @param n
     * @return
     */
    public static long factorial(int n){
        if(n == 0 || n == 1){
            return 1;
        }
        return n * factorial(n - 1);
    }

    /**
     * 阶乘尾部有多少个0
     * @param n
     * @return
     */
    public static int trailingZeroes(int n){
        int res = 0;
        while (n >= 5){
            res += n / 5;
            n = n / 5;
        }
        return res;
    }
}