# Is Determining the Number of distinct Prime Factors Polynomial?

Our current understanding of prime factorization states that it is hard to solve. The problem asks us to find the list of prime factors for an integer. For example, 18's prime factors are 3, 3, and 2. But since 3 is repeated, we only count it once.

But what about a slightly easier problem---finding how many prime factors a number has. Is there an efficient algorithm to do such a task?

In the 18 case, we still don't double count 3. So our algorithm should output 2 (the two prime factors are 3 and 2).

• You are essentially asking for the complexity of computing the prime omega function $\omega(n)$. Commented Nov 5, 2023 at 18:07
• @Steven I edited the question to say that prime factorization is hard to solve as we currently know it Commented Nov 5, 2023 at 18:24
• mathoverflow.net/q/3820/37212
– D.W.
Commented Nov 6, 2023 at 5:12

It’s easy to find small prime factors. Pollard-rho can find a factor p in $$O(\sqrt p)$$ which finds many prime factors. And for large n with no known small prime factors we can do a primality test which finds there is one factor only.
The problem is when n is so large that we cannot prove there are no factors up to $$n^{1/3}$$ so we don’t know if there are 2 or 3 prime factors.