# Euler's totient function maximum value for a range [duplicate]

This question already has an answer here:

For the euler's totient function, we have a number $n<10^{18}$

we have to find the value of $i$ between $2$ and $n$ (both inclusive) such that the value of $\phi(i)/i$ is maximum.

I have have observed that this value will be equal to the largest prime number less than or equal to n. Now since $n$ is upto $10^{18}$, what will be the most efficient way to do this?

## marked as duplicate by Marc van Leeuwen, Dennis Gulko, Davide Giraudo, Julian Kuelshammer, azimutMay 5 '13 at 9:55

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 1 Answer

Hint:

$\phi(p)=p-1$, so now you have to look for largest prime before $10^{18}$

• din't i mention that above already? – Salena May 5 '13 at 8:18
• Write a program to find out a largest prime before 10^{18}. – Inceptio May 5 '13 at 8:28
• Even for $i=p^m$, $\phi(i)/i=(p-1)/p$, so need to look for primes and prime powers! – Karthik C May 5 '13 at 8:31
• @AneeshKarthikC: When $i=p^m$, $\phi(i)=p^m(\dfrac{p-1}{p})$, right? – Inceptio May 5 '13 at 8:34
• $\phi(i)/i$ I remarked about – Karthik C May 5 '13 at 8:42