Waste less time on Facebook — follow Brilliant.

Prime Factors

Is there a theorem that describes how many prime factors a number has? And does this this theorem have a solution on how to find them?

Note by Gabriel Kong
4 years, 3 months ago

No vote yet
2 votes


Sort by:

Top Newest

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? Peter Lynn · 4 years, 3 months ago

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)? Peter Lynn · 4 years, 3 months ago

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. Gabriel Kong · 4 years, 3 months ago

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? Gabriel Kong · 4 years, 3 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...