# 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;

kitchent + 2 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

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

rvcenaveed + 0 comments Hi Guys,

Can we get test cases which are being executed here, I am able to see results for all the possible test cases in my local. and they seem to paas. But when i submit it says runtime error, time out etc. Can we get list of testcases that system is trying run ?

bnavkri + 1 comment Any idea what could be there in test cases 3,4,5 and 6? I did prog in python and getting runtime errors. thx

bh2smith + 0 comments I'd guess you have a for loop that exceeds 10^8. I haven't actually managed to pinpoint the exact cutoff, but its somwhere between 10^7 + 5*10^6 and 10^7 + 6*10^6.

bnavkri + 0 comments Any idea what could be there in test cases 3,4,5 and 6? I did prog in python and getting runtime errors. thx

Ethan_Barner + 1 comment Het

rupinder73singh + 0 comments [deleted]

No more comments

Sort 9 Discussions, By:

Please Login in order to post a comment