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.