# 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
Commented May 9, 2019 at 2:37
• Consensus is that finding number of prime factors is not significantly easier than factoring. Commented May 9, 2019 at 4:03
• Do you want repeated prime factors counted? e.g., 12 has three prime factors, two distinct. Commented May 9, 2019 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? Commented May 9, 2019 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.
– user645636
Commented May 9, 2019 at 14:51

Actually, a semiprime with unknown prime factors was constructed with methods of elliptic curves.

Despite of this, in general, determining the repeated number of prime factors (often called big-omega) is not significantally easier than factoring , at least no such algorithm is currently known.

Checking for perfect powers and trial division can clarify things for small numbers, but only in very special cases, big-omega can be faster determined than the prime factorization.