Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How do I approach this problem using unique factorization?...

How many numbers are product of (exactly) $3$ distinct primes $< 100$?

edit: Just to add to that, How does unique factorization into primes play an important role in answering this question?

share|cite|improve this question
Are the numbers that are the product of exactly 3 distinct primes less than a 100, or are the primes less than 100? In the latter case, count how many primes less than 100 there are, then count how many ways there are of picking three distinct ones out of that set. In the former, it's a bit trickier. – Arturo Magidin Dec 13 '11 at 20:50
@ArturoMagidin its primes less than 100. I know there are exactly 25 primes < 100 – Gregslu Dec 13 '11 at 20:57
@ArturoMagidin the question would be 'How many numbers are the product of exactly 3 distinct primes less than 100?' this gives an oppurtunity to make use of unique factorization of primes – Bhargav Dec 13 '11 at 20:58
@168335 I have no idea how you are getting that... If $p$, $q$, and $r$ are the three primes, then how many times did you count them when you computed $25\times 24\times 23$? Once each for $p,q,r$; $p,r,q$; $q,p,r$; $q,r,p$; $r,p,q$; $r,q,p$. So just divide by $6$. Or, use the formula for combinations instead of permutations. – Arturo Magidin Dec 13 '11 at 21:19
Note that the ordinary meaning of the question is that the product is less than $100$. So if the question was posed, in English, exactly as written, then the answer $\binom{25}{3}$ is incorrect. – André Nicolas Dec 13 '11 at 22:17
up vote 5 down vote accepted

So, you want to count the number of integers $n$ that can be written as $$n = pqr,$$ where $p$, $q$, and $r$ are pairwise distinct primes, each less than a 100. By unique factorization, it suffices to first pick the three distinct primes and then multiply them together.

You've counted that there are 25 primes less than 100. You want to pick three of them. How many ways are there to do so?

share|cite|improve this answer
2300? not sure if correct. – Gregslu Dec 13 '11 at 21:19
It would help you to make sure whether you are correct if instead of just spitting out the number, you attempted to explain your reasoning to obtain that number. – Arturo Magidin Dec 13 '11 at 21:21
Using binomial coefficient 25C3 = 2300, its a tricky question. – Gregslu Dec 13 '11 at 21:40
@Gregslu: What exactly is tricky about it? You have 25 things to choose from, you want to choose three of them, the answer is $\binom{25}{3}$. No tricks at all. – Arturo Magidin Dec 13 '11 at 21:44
(+1) and a nomination for "Most patient, 2011". – The Chaz 2.0 Dec 13 '11 at 23:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.