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.

2.Optimizing the prime factorizing algoritm, I’m unsure about this.