We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- All Contests
- ProjectEuler+
- Project Euler #70: Totient permutation

# Project Euler #70: Totient permutation

# Project Euler #70: Totient permutation

_{This problem is a programming version of Problem 70 from projecteuler.net}

Euler's Totient function, [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to which are relatively prime to . For example, as and are all less than nine and relatively prime to nine, .

The number 1 is considered to be relatively prime to every positive number, so . Interestingly, , and it can be seen that is a permutation of .

Find the value of , , for which is a permutation of and the ratio produces a minimum.

**Input Format**

Input contains an integer

**Constraints**

**Output Format**

Print the answer corresponding to the test case.

**Sample Input**

```
100
```

**Sample Output**

```
21
```