This post is an extension to make an optimization in precomputing the values of Totient and Mobius function. So make sure you first go through the previous post.
The extra initialization required for Algorithm 2 made me think for a while to eliminate the 'initializing' for loop. So I made (or atleast tried to make) a little optimization there. I realized that we don't need that loop. Instead, I initialized the values in the for loop only when the EulerPhi was zero. In other words, when we first reach a number, we do the initialization which should be sufficient enough. The following algorithm do that.
The extra initialization required for Algorithm 2 made me think for a while to eliminate the 'initializing' for loop. So I made (or atleast tried to make) a little optimization there. I realized that we don't need that loop. Instead, I initialized the values in the for loop only when the EulerPhi was zero. In other words, when we first reach a number, we do the initialization which should be sufficient enough. The following algorithm do that.
Algorithm 3
function PRECOMPUTATION(n)
flag $\gets$ [0] * (n)
EulerPhi $\gets$ [0] * (n)
Mu $\gets$ [0] * (n)
Primes $\gets$ [0] * (n)
pos $\gets$ 1
for i = 2 to n do
if flag[i] = 0 then
for j = i to n do
flag[j] = 1
if EulerPhi[j] = 0 then
EulerPhi[j] $\gets$ j
Mu[j] $\gets$ 1
endif
EulerPhi[j] $\gets$ ( EulerPhi[j] / i ) * ( i– 1 )
if j/i%i = 0 then
Mu[j] $\gets$ 0
else
Mu[j] $\gets$ Mu[j] * (-1)
end if
j $\gets$ j + i
end for
Primes[pos] $\gets$ i
pos $\gets$ pos +1
end if
end for
return Primes
return EulerPhi
return Mu
end function
Yours Aye
Me
No comments:
Post a Comment