D - Factorial and Multiple Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

2 以上の整数 K が与えられます。
正の整数 N であって、N! が K の倍数となるようなもののうち最小のものを求めてください。

ただし、N! は N の階乗を表し、問題の制約下で、そのような N が必ず存在することが証明できます。

制約

  • 2\leq K\leq 10^{12}
  • K は整数

入力

入力は以下の形式で標準入力から与えられる。

K

出力

N! が K の倍数となるような最小の正整数 N を出力せよ。

入力例 1

30

出力例 1

5
  • 1!=1
  • 2!=2\times 1=2
  • 3!=3\times 2\times 1=6
  • 4!=4\times 3\times 2\times 1=24
  • 5!=5\times 4\times 3\times 2\times 1=120

より、N! が 30 の倍数となる最小の正整数 N は 5 です。よって、5 を出力します。

入力例 2

123456789011

出力例 2

123456789011

入力例 3

280

出力例 3

7

Score : 400 points

Problem Statement

You are given an integer K greater than or equal to 2.
Find the minimum positive integer N such that N! is a multiple of K.

Here, N! denotes the factorial of N. Under the Constraints of this problem, we can prove that such an N always exists.

Constraints

  • 2\leq K\leq 10^{12}
  • K is an integer.

Input

The input is given from Standard Input in the following format:

K

Output

Print the minimum positive integer N such that N! is a multiple of K.

Sample Input 1

30

Sample Output 1

5
  • 1!=1
  • 2!=2\times 1=2
  • 3!=3\times 2\times 1=6
  • 4!=4\times 3\times 2\times 1=24
  • 5!=5\times 4\times 3\times 2\times 1=120

Therefore, 5 is the minimum positive integer N such that N! is a multiple of 30. Thus, 5 should be printed.

Sample Input 2

123456789011

Sample Output 2

123456789011

Sample Input 3

280

Sample Output 3

7