ECOO '18 R2 P3 - Factorial

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 13.0s
Memory limit: 256M

Problem type

The factorial of a number N, denoted as N!, is equal to the product of all natural numbers up to and including N. For example,

  • 1!=1
  • 2!=1\times2=2
  • 3!=1\times2\times3=6
  • 4!=1\times2\times3\times4=24

Given two numbers K and M, what is the smallest value of N such that N! has at least M factors of K (that is, K^M divides evenly into N!)?

Input Specification

The standard input will contain 10 datasets. Each dataset contains two integers K, M (2 \le K,M \le 1\,000\,000).

For the first 4 cases, K is prime and K \times M \le 1\,000.

For the first 7 cases, K \times M \le 1\,000\,000.

Output Specification

For each dataset, output the minimum value of N such that N! has at least M factors of K.

Sample Input (Five Datasets Shown)

2 2
2 3
3 1
4 2
10 10

Sample Output


Educational Computing Organization of Ontario - statements, test data and other materials can be found at


There are no comments at the moment.