This problem is also about totient function, but it is not so straight forward to find an efficient solution.
I do not have my old code, so I first factored all number and calculate phi(n). It is obvious that this is not a good choice. It takes 8 second to get the answer(debug version). I am not satisfied with this solution. So I used a sieve method to compute all number's totient function. This is better, it takes 5 second in debug version and 1 second in optimized version to get the answer.
No comments:
Post a Comment