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  &amp;\text{if $n$ is odd} \\
-1 &amp;\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&gt;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.
The reason I'm interested in this is to graph the function, My current code is the first thing that went into my head, i.e, very nonoptimal.
This function is related to Liouville function.
Algorithm in the question
Although it is correct, it is rather slow. In the function Omega(k), b goes from 1 to the largest prime divisor of $k$, which is of order $\dfrac {\pi^2n} {12\,\log n}$ on average for $1 \le k \le n$ as mentioned by the On-Line Encyclopedia of Integer Sequences. So, the running time of computing $g(n)$ is $O(\dfrac {n^2}{\log n})$. It takes more than an hour to compute $g(10^6)$ on my computer.
A Faster Algorithm
Instead of computing directly the number of prime factors of each number $k$, we can add 1 to $\Omega(k)$ whenever $k$ is a multiple of a power of $p$ for all primes $p$. For example, since 72 is a multiple of 2, 4, 8, 3 and 9 but no other powers of primes, we will get
$$\Omega(72)=(1+1+1)+(1+1)=5.$$
Here is the improved algorithm.
def g(n):
    # Omega[k], for k &gt;= 1, is the total number of prime factors
    # of k, honoring their multiplicity. Omega[0]=0 is ignored.
    Omega = [0] * (n+1)
    for k in range(2, n+1):
        if Omega[k] == 0:  # i is a prime.
            power = k
            while power &lt;= n:
                m = power
                while m &lt;= n:
                    Omega[m] += 1
                    m += power
                power *= k

    return sum(map(lambda x: (x % 2 * 2 - 1) * x, Omega))


On average, each $O(1)$ number of operations will yield 1 prime factor. Thus, the running time of the algorithm above is
$$O(1)\cdot O\left(\sum_{k=1}^n\Omega(k)\right)=O(n\log\log n),$$
where $\log\log n$ is the average of $\Omega(i)$ for $1\le i\le n$, as mentioned in Wikipedia. Since $\log\log n$ grows very slowly, this algorithm can be considered as an almost linear algorithm.
It took less than 1 second to run g(10^6) on my computer.