Project Euler #70: Totient permutation

  • + 1 comment

    I am one of those who approach the problem using the property that is minimum when it is prime. And because is never the permutation of prime , so we set our sight on being the product of two primes and . (Hint on counting: )

    For my implementation, I used a prime sieve to generate a list of primes, and feed them to a 2-level for loop afterwards. The point here is the find a balance between reducing the size of prime sieve (otherwise it would be TLE if we make a sieve of size ) and whether we have enough primes to get to the answer. For example, one of the answers is (product of and ), so we need to ensure is included in the prime sieve when is .

    Apart from that, we have one honourable candidate who is an answer, but is not the product of two prime numbers, but three! This is the frustrating Test Case #10. I don't have a strategy yet to handle this other than treating it as a special case.