How do i calculate Σ phi(m) as m varies from 1 to n efficiently?
Note : Calculating each separately and adding them takes O(n^2).
Is there a more efficient algorithm?
n<=10^6
2 Likes
Yes there is and it uses the sieve.
If you provided the limit of n it would be good but nevertheless I will tell you my method.
The main problem in calculating the totient function for each number is that you have to search till sqrt(i)[to calculate the totient function of i].
In short if we could just decrease the time taken for prime factorization for i we would considerably increase the speed of the program.
The way to do that is in using sieve to solve this problem.
What we do in sieve is find primes upto a given number (in this case it is n).
Every time we mark a multiple of a prime instead of marking it with 1 we just mark it by the prime.
This means that just whenever marking composite from the primes just mark them with the prime , this way for each number you know it’s starting prime number and hence no need to search till sqrt(i). Just use the array you used to mark composites in the sieve and it will till you ith numbers first factor and then you would have reduced sqrt(i) to a constant number of iterations.
Then after calculating the totient of each number just sum it up and give the answer.
I don’t know exactly the complexity of this method but it’s pretty much O(n) for n<=10^7.
Using Seive you can calculate phi of all the numbers between 1 and n in O(nlogn) and adding them takes O(n).
However it can be done in nearly O(n^(2/3)logn) by precalculating a function called g(x)=Σ phi(m) as m varies from 1 to x. till x=n^2/3 using sieve
and using recursion
g(x)=x(x+1)/2-Σ g(m) as m varies from 2 to x. However it is not required here as n<10^6.
4 Likes