Suppose you are given a number $n$ and told that the sum of its prime factors is $s$. I'm looking for an efficient algorithm that checks the truth of the statement.
Obviously one can simply calculate the factorization of $n$, add, then check if the result is equal to $s,$ but it seems that the problem can be easier. For example, if $s\approx n/100$ then $n$ must be contain at least one large prime which can be discovered by trial division. Can this be formalized? Are there other properties that can be used?
In my immediate case the sum is with multiplicity (so the sum of the prime factors of 1024 is 20) but I would be interested in the case where multiplicity is ignored (giving 2). Similarly, in the problem at hand I am interested in small n ($n<10^{12}$) but approaches that apply to larger numbers are welcome.
This isn't state of the art, but for your purposes it may be sufficient. You can implement Sieve of Eratosthenes using a dynamic programming approach.
It obviates the need to do any trial division and instead gives you trade off between upfront initialization and, roughly speaking, constant time look-up.
Let $T[i]$ denote the smallest prime, $p$, factor of $i$. To find the total factoring of $i$, start at $T[i]$ and record its value. Then, go to $T[ i / T[i] ]$ and record its value. If $i = T[i]$ terminate, otherwise continue until it does.
Take a second pass over the factoring table to evaluate the sum of factors in a similar way to build a sum of factors look-up table.
This process should take 3-5 secs (depending on your hardware) to build the sum of factors for all n between two and $10^8$.
Downside to this approach is that is not easily distributed or parallelized.
For a more concrete implementation, you can read my write-up of this approach from a couple years ago: http://antimatroid.wordpress.com/2009/04/01/integer-factorization-by-dynamic-programming-with-number-theoretic-applications/