I am becoming more and more addicted to the Project Euler problems. However since one week I am stuck with the #214.

Here is a short version of the problem: PHI() is Euler's totient function, i.e. for any given integer n, PHI(n)=numbers of k<=n for which gcd(k,n)=1.

We can iterate PHI() to create a chain. For example starting from 18:

PHI(18)=6 => PHI(6)=2 => PHI(2)=1.

So starting from 18 we get a chain of length 4 (18,6,2,1)

The problem is to calculate the sum of all primes less than 40e6 which generate a chain of length 25.

I built a function that calculates the chain length of any number and I tested it for
small values: it works well and fast.
sum of all primes<=20 which generate a chain of length 4: 12
sum of all primes<=1000 which generate a chain of length 10: 39383

Unfortunately my algorithm doesn't scale well. When I apply it to the problem, it takes several hours to calculate... so I stop it because the Project Euler problems must be solved in less than one minute.

I thought that my prime detection function might be slow so I fed the program with a list of primes <40e6 to avoid the primality test... The code runs now a little bit faster, but there is still no way to get a solution in less than a few hours (and I don't want this).

So is there any "magic trick" that I am missing here ? I really don't understand how to be more efficient on this one...

I am not asking for the solution, because fighting with optimization is all the fun of Project Euler. However, any small hint that could put me on the right track would be welcome.

Thanks !