# Project Euler #69: Totient maximum

# Project Euler #69: Totient maximum

khoangcachxalam1 + 0 comments attention : if p is prime p^k/phi(p^k) = p^(k-1)/phi(p^(k-1))=...= p/p-1;

K_Abhishek + 0 comments hint:- if we see here from the description table ,the prime no. has more no. of relative primes. 1 is considered as relative prime for every no. for n/phi(n) should be large ,phi(n) should be small and n should be large. just consider n as product of prime no.and check whether its smaller than the given limit. phi(n)=n*(1-(1/p)), where p is prime.

kitchent + 3 comments I wonder how people would attempt to solve this problem if the ratio itself is required as part of the output.

tieros + 0 comments I did it on projecteuler when I first solved the problem. Hint is sieve, fast and easy :)

Edit: Just checked it with (10**18)**0.5 (10**9) and it caused memory error, with so big upper bound I guess time limit will never enough.

kukreja_vlk + 0 comments As @tieros suggests sieve is fine for 10^6 input, but for higher n, we can directly find the factors of the given ans (as the ans can be found in O(1) time). Time complexity would be dependent on the time taken to find factors O(sqrt(N)) as per Factors time complexity

qayum_khan_usa + 0 comments That would be equally easy. Think hard about khoangcachxalam1's observation, then what happens for composite numbers, and finally about how that observation behaves as the prime

`p`

approaches infinity (for a rigorous proof). This led me to find a solution with no non-input array exceeding length`15`

despite`N`

going up to`1e18`

.Though long integers are needed ephemerally for very large

`N`

, I even avoided`float`

arrays! If you are more experimentally minded, generate a table of`n / phi(n)`

for`1 < n < 212`

and watch what happens to those floats — that's what I did, just to make sure.

mejariamol + 1 comment what is runtime error

shashank21jHackerRank AdminChallenge Author + 0 comments

andreymir + 1 comment TCs 4, 5, 7 are failing with Wrong Answer. Any ideas what could be wrong?

shashank21jHackerRank AdminChallenge Author + 0 comments If you solve the original PE problem you will get the solution there itself

Sort 10 Discussions, By:

Please Login in order to post a comment