You just jumped the gun on me. I was going to say that I doubt that there is such a solution. If there were, it would be a test for primality. Tests for primality are expensive to computer. The simplest one is to factor the given number, which would answer your question but is computationally difficult for numbers of even moderate length.

Look into the Euler Totient Function, and notice that computing it for large numbers seems to call for factorizing those numbers. My COMPLETE GUESS is that there is no better theorem for counting the prime factors than factorizing the number and counting them.

Have you read something like the overview in Wikipedia on primality tests? They are not simple.

Since the above is a guess, does anyone out there actually know the answer?

Haha. The answer to my last question would seriously have a great impact on math theory, worth asking anyway. Haha. About the theorem, I see that we have a similar opinion. I just shot the question in hope that there's some deep math theory about prime factors which might be beyond my knowledge. Thanks a lot by the way.

The second one. I'm interested on how to find those factors for any given number. And can I also add another question? Is there a way on finding whether a given number is prime?

## Comments

Sort by:

TopNewestYou just jumped the gun on me. I was going to say that I doubt that there is such a solution. If there were, it would be a test for primality. Tests for primality are expensive to computer. The simplest one is to factor the given number, which would answer your question but is computationally difficult for numbers of even moderate length.

Look into the Euler Totient Function, and notice that computing it for large numbers seems to call for factorizing those numbers. My COMPLETE GUESS is that there is no better theorem for counting the prime factors than factorizing the number and counting them.

Have you read something like the overview in Wikipedia on primality tests? They are not simple.

Since the above is a guess, does anyone out there actually know the answer?

Log in to reply

How many distinct prime factors or how many non-one primes multiply out to it? Does 12 have 2 prime factors (2 and 3) or 3 (2, 2, and 3)?

Log in to reply

Haha. The answer to my last question would seriously have a great impact on math theory, worth asking anyway. Haha. About the theorem, I see that we have a similar opinion. I just shot the question in hope that there's some deep math theory about prime factors which might be beyond my knowledge. Thanks a lot by the way.

Log in to reply

The second one. I'm interested on how to find those factors for any given number. And can I also add another question? Is there a way on finding whether a given number is prime?

Log in to reply