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 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.