Corectness of Prime Factorization over a range Here is an algorithm for counting the total prime factors of all positive natural numbers $\le N$.
Initially $f_{i} = 1$ for all $1 \le i \le N$
loop i from 2 to N
    if f[i] = 1 then
        loop j from 2 to N
            f[j * i] = f[i] + f[j]
    endif

Is the algorithm correct? If so why?
Well I checked where the algorithm could fail
if i = 2, then f[2 * 15] = f[2] + f[15]
But f[15] = 1, since $i \lt 15$.
But eventually f[30] = f[5 * 6] = f[5] + f[6].
The result becomes correct.
 A: Here is a proof:
1) Let $p(n)$ be the number of prime factors of $n \in \mathbb{N}, n\ge 2$. The algorithm uses the basic fact from number theory, that $p(m \cdot n) = p(m) + p(n)$.
2) In each iteration of the outer loop, $i$ is a prime if and only if $f[i]=1$. If this is not clear to you, check out the proof of the Sieve of Eratosthenes. While in the Sieve of Eratosthenes numbers usually are flagged as being composite by setting a boolean flag, this algorithms "flags" the numbers by assigning a value greater than 1 to the according field in the array $f$.
3) As it's easy to see, the algorithm overwrites some fields in $f$ many times. So if we are interested in the correctness of the final result of the alogorithm, we have to see, which value is finally assigned to a field of $f$. For any field $k \in \{2, ..., N\}$ this happens exactly when the loop variables $i$ and $j$ are so that $i \cdot j = k$ and $i$ is the largest prime factor of $k$. This is what Daniel mentioned in his comment, and it follows from 2).
Now we prove by induction: $\forall k \in \{2, ..., N\}: f[k] = p(k)$ after the algorithm terminates.
For $k=2$ this is clear.
Let's assume that it is true for $2, ..., k-1$. Let $i,j$ be the indices of the loops when $f[k]$ becomes finally assigned, so we have $i \cdot j = k$. As stated in 3), $i$ is the largest prime factor of $k$. In the following we want to show that $f[j]$ has already been finally assigned and that $f[j] = p(j)$.
Since $j$ is a divisor of $k$, all prime factors of $j$ are less or equal $i$. Let $t \le i$ be the largest prime factor of $j$. Then we have two cases:
$t < i$: In the $i$-th iteration of the outer loop we've already passed the $t$-th iteration. So because of 3), $f[j]$ has already been assigned to it's final value. 
$t = i$: Let $z \in \mathbb{N}$ so that $j = i \cdot z$. $i$ is the largest prime factor of $j$, so $j$ becoms also finally assigned in the $i$-th iteration of the outer loop, but in the $z$-th iteration of the inner loop. Because of $z < j$, we have already passed the $z$-th iteration of the inner loop, when we are in the $j$-th iteration of the inner loop. So $f[j]$ has already been assigned to it's final value.
Because of $j < k$ and the induction hypothesis, we know $f[j] = p(j)$. So using 1) we get
$f[k] = f[i]+f[j] = p(i)+p(j) = p(i \cdot j) = p(k)$. 
This shows, that the algorithm assigns the correct value to $f[k]$.
q.e.d.
Don't hesitate to ask for clarification if anything is unclear.
By the way, this is a very interesting algorithm that obviously runs in $O(N\cdot Primes(N))$, where $Primes(N)$ is the number of prime numbers within $2, ..., N$. As far as I know, there are good small estimates for $Primes(N)$ in number theory. So this seems to be very efficient, though I don't know whether there is a more efficient algorithm.
