Project Euler 512 - Sums of totients of powers

Official link:

Note: My code takes around ~1000s

Thought Process

The question is now reduced to make an efficient sum of totient algorithm. I made a simple modified sieve.

  1. Initialise an array, phi, where phi[x] = x, and a sum of even numbers using (n/2)*(2a + 2(n-1))

  2. loop through phi from 3 to limit, skipping 2 (Because even numbers can't be primes)

    1. If phi[x] = x, then it is a prime, p, because it hasn't been seen yet, remove one from it because (phi(p) = p-1)

    2. Using the current prime, loop through from 3*p to the limit, skipping 2*p (because we don't care about the even numbers and remove phi[x] div p

  3. Return the sum of the odd numbers in the array

It works, but it is not very efficient. I am going to try to make a better code at some point, but it will do for now

Interactive Code

Input an integer (yourinput)

Code will output g(yourinput)