Informatica Online Judge

  Euler Phi Function(Large) [0679 / 02A7]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 11   Total Tried : 19


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

n이하의 양의 정수들 중 n과 서로 소인 정수의 수를 φ(n)로 표현하며, 이를 오일러 파이함수라고 한다.

예를 들어 9와 서로소인 양의 정수는 1, 2, 4, 5, 7, 8이므로 총 6개가 있다. 따라서 φ(9)=6이다.

그리고 정수 1은 모든 수의 소인수로 취급할 수 있으므로, φ(1)=1이다.

몇몇 정수들은 재미있는 성질을 가진다. 예를들어 87109의 파이함수의 값은 φ(87109)=79180이다. 즉, 87109는 그 함수값이 원래 수와 순열관계에 있다.

임의의 정수 n(<=10^9)이 주어질 때, n과 φ(n)이 순열관계이면서 n/φ(n)의 값이 가장 작은 n값을 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 한 정수 n이 입력된다. (단, n은 1,000,000,000이하의 양의 정수)

Output

n과 φ(n)이 순열관계이면서, n/φ(n)이 가장 작은 정수 n을 출력한다.

IO Example

입력
35

출력
21

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]