Common Factors

Photo by Bob Chao

Everyone likes to share things in common with other people.

Numbers are the same way! Numbers like it when they have a factor in common.

For example, $4$ and $6$ share a common factor of $2$, which gives them something to talk about.

For a given integer $n$, we define a function, $f(n)$, equal to the number of integers in the range $\left[1, n\right]$ that share a common factor greater than $1$ with $n$.

Furthermore, we can define a second function, $g(n)$, which characterizes the fraction of numbers that like a given number as follows: $g(n)$ = $\frac{f(n)}{n}$

What we really want to know though, is, for any integer $2 \leq k \leq n$, what is the maximum value of $g(k)$?


The input consists of a single integer $n$ ($2 \leq n \leq 10^{18}$), the value of $n$ for the input case.


For the provided test case, output the result as a fraction, in lowest terms, in the form $p$/$q$ where the greatest common divisor of $p$ and $q$ is $1$.

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 5.0medium
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in