# Algorithm that returns the number of prime factors (non-distinct) of an integer WITHOUT finding the prime factorization

Currently, the most efficient algorithm that classical computers can use to factor large composite numbers is the General Number Field Sieve (GNFS), which runs in subexponential time. It returns a set of primes that, when multiplied, yield the composite. Is there such an algorithm that will return the number of primes that a composite number is composed of without actually factoring it, that runs in polynomial time (or better)? Assuming the convention that one is not prime, if the input is already prime, the result will be one.

• So, you want a fast algorithm for the prime Omega function. – lhf May 9 at 2:37
• Consensus is that finding number of prime factors is not significantly easier than factoring. – Gerry Myerson May 9 at 4:03
• Do you want repeated prime factors counted? e.g., 12 has three prime factors, two distinct. – Robert Soupe May 9 at 4:13
• @Robert, does it matter? Is there a significant difference in the computational complexity when you count primes with multiplicity, or when you don't? – Gerry Myerson May 9 at 12:26
• @GerryMyerson factoring without multiplicity, is factoring the radical which for cases like $5040=2^43^25^17^1$ is $210=2^13^15^17^1$ which is 1 in 24 of the original. – Roddy MacPhee May 9 at 14:51