Totient Function

C++. This is the Problem 69 from Project Euler.

Question: Euler’s Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10. Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum. Link to the page.

Solution: Please check those reference links to see how Totient function works: Link1 and Link2 To make the implementation efficient, analysing the sequence for a small quantity is important. When we observe, we see that Phi is lesser for even numbers than the next consecutive odd numbers. That means that only even numbers will make the ratio is higher. Therefore, we only check even numbers in input n, particularly for big values. Plus, I used float data type instead of double for efficiency by trading with precision. So there is a small rounding error at the calculation of Phi at some points. However, it does not affect the result and the rounding error is neglectable. The answer is 510510, and Phi is 92160 for the input 510510.