Factorials divisor

Time Limit: 1 sec

 

The Problem

In this problem given two numbers N and M. M will always be a prime number. In this problem you have to find out how many times M will occur when you prime factorize the N factorial (N!).

 

For example

N = 6 and M = 3

N! = 1*2*3*4*5*6 = 720

Prime factorization of 720 or N! is

720 = 2 * 2 * 2 * 2 * 3 * 3 * 5.

Here 3 occur 2 times. So 2 is the answer for N=6 and M=3.

 

The Input

The input file will contain several lines of input. Each line of input will contains two positive integers N (1<=N<=10^15) and M (1<M<100000). Input is terminated by EOF.

 

The Output

For each lines of input print one lines of output which contains a single positive integers P the number of M occurs in prime factorization of N!. If there is no M in N!, then print “NULL”.

 

Sample Input

5 2

8 3

10 11

10 5

 

Sample Output

3

2

NULL

2

 

 

 

Inter University Programming Contest - 2017 [BGC Trust University Bangladesh]

Problem Setter: Parag Paul