# algorithms – optimizing the calculation of \$sum^n_{k=2} p(Omega(k))Omega(k)\$

I want to optimize an algoritm for calculating $$g(n)=sum^n_{k=2} p(Omega(k))Omega(k)$$
where $$p(n) = begin{cases} 1 &text{if n is odd} \ -1 &text{if n is even} end{cases}$$
and $$Omega(n)$$ is the prime factor counting function or more exactly, I want to optimize calculating all it’s values up to $$n$$
my current best try is

``````def Omega(k):
Factor = 0
b=1
while(k>1):
b +=1
if (k % b == 0):
while k % b == 0:
k /= b
Factor += 1
return Factor
sum = 0
for i in range(n)
w = Omega(i)
sum += ((w%2)*2-1)*w
#using it
``````

First, I am trying to calculate the current algorithm’s computational complexity.
we calculate $$Omega(k) ~~n$$ times, I haven’t managed to calculate $$Omega(k)$$‘s computational complexity but it seems to be $$O(sqrt k log k)$$ thus, I think the entire program is $$O(n^{1.5} log n)$$.
Am I correct?
Can any of you help optimize my algoritm?
Note: Is this the correct exchange for this question?
Ideas:
1.Calculating $$Omega$$ less,$$Omega$$ is an Completely Additive function, i.e. for any $$a,b$$, $$Omega(ab)=Omega(a)+Omega(b)$$, I’ve tried to use this to optimize the calculation, but have not managed to.