Cho một số nguyên dương \(n\) và một số nguyên tố \(p\). Hãy tìm ra bậc lũy thừa của \(p\) trong phân tích thừa số nguyên tố của \(n!\). Ví dụ \(n = 4, p = 2\) phân tích thừa số nguyên tố của \(4! = 24 = 2^3 \times 3\) vậy bậc lũy thừa của \(2\) trong phân tích thừa số nguyên tố \(4!\) là \(3\).

INPUT FORMAT

Dòng đầu tiên chứa giá trị \(n, p (1 \leq n, p \leq 10^{9})\).

OUTPUT FORMAT

In ra một số duy nhất là kết quả của bài toán.

Ví dụ 1:

Input

4 2

Ouput

3

Ví dụ 2:

Input

24 2

Output

22

Bài tập này: E: Khó

Giải thích ví dụ mẫu:

• Ví dụ 1:

  • Input: 4 2
  • Output: 3
  • Giải thích: Phân tích thừa số nguyên tố của 4! là 2^3 × 3. Bậc lũy thừa của 2 trong phân tích này là 3.

• Ví dụ 2:

  • Input: 24 2
  • Output: 22
  • Giải thích: Phân tích thừa số nguyên tố của 24! có bậc lũy thừa của 2 là 22.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House