4
$\begingroup$

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?

$\endgroup$

marked as duplicate by Marc van Leeuwen, Dennis Gulko, Davide Giraudo, Julian Kuelshammer, azimut May 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
$\begingroup$

Hint:

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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.