Do you know how to factor the numbers from 1 to N in O(NlogN) time? It's a simple modification to the standard Sieve of Erastosthenes. That's a start.

The next step is to look at the formula for phi(n) that uses the factorization of n.

The Memory complexity of modified-sieve-algorithm (for factorization of integers) should be O(N), not O(N lgN).

(I used just 4 arrays of size 2000000, and used memory is almost 30000.

You shouldn't use more than 4 linear-arrays, or you'll get MLE.)

for each integer v ∈ [1...N],

store the prime factor factor[v] that divides v.

And, another hint :

factorization of 72 can refer factorization of 9, if factor[72] is 2.

The formula for phi(n) that uses the factorization of n is this if I am not mistaken: phi(n) = n*(1 - 1/p1)*....*(1- 1/pr) if the prime factors of n are p1, ... to pr. This can be rewritten as (n/p1...pr)*phi(p1)*...*phi(pr)

However my approach modifying the sieve and using this formula is still slow (about 1.2s on the OJ without I/O operations - I used 1 submission to time it and about 1.3s on my PC) as I am running the "full" sieve compared to those whose code run is < 1s

By "full" sieve I mean that I let the sieve continue after sqrt(2000000) which is about 1414 rather than let the sieve stop at 1414 so that all primes are handled. So my code is actually O(n^2) rather than O(n log n). It was mentioned in the above quote that it is possible to compute all phi(n) where n = 2000000 in O(n log n).

I used 3 arrays - 1 to store phi(n) for each n, one to store depthphi(n) fpr each n, and one to store sum(depthphi(i)) for i from 2 to n. the sum and depthphi are computed using DP and the bottleneck in my code is the code for computing phi(i).

I don't quite get the hints mentioned. Could someone give me a push in the right direction as to how to speed up my code? Thanks.