Project Euler 214 - Totient Chains

Official link:

Thought Process

I just made a simple totient sieve loosely based on one I made for problem 512, while i'm at it I also add all the primes I find so that I don't have to do a second sieve.

Once I have my sieve I simply just loop through all the primes and find their chain length (which I can now do quickly with my pore-computed totient sieve) and I get the answer in a reasonable 52 seconds.

Some small things were added to speed up the code:

  1. There is a prime such that no primes below it can generate a chain of length 25, cuts out of good chunk of useless checking, but I leave it to you to find it

  2. Implement a quick stop if your chain length is longer than 25

Interactive Code

Enter 2 numbers (limit, chain_length)

Code will output the sum of all primes less than limit that make a chain length of length chain_length