1
$\begingroup$

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?

  • 3
    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.2011-12-13
  • 0
    @ArturoMagidin its primes less than 100. I know there are exactly 25 primes < 1002011-12-13
  • 0
    @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 primes2011-12-13
  • 0
    you are looking for numbers of the form n=pqr where p,q,r are primes. since u already said there are 25 primes less than 100, total number of such numbers would be 25x24x23. Is this that easy or am i missing something?2011-12-13
  • 0
    @168335: So, $3\times 5\times 7$ gives a different number than $5\times 3\times 7$?2011-12-13
  • 0
    oops u r right, my method doesnt account for the repitions, well i will have to look deeper now2011-12-13
  • 0
    @ArturoMagidin exactly 3 distinct primes therefore 2^2×3×5 wont work.2011-12-13
  • 0
    @ArturoMagidin so lets say p,q,r, have to be in increasing order (so as to remove repitions). then the total number of such numbers is 24x23 + 23x22 +22x21+......+2x12011-12-13
  • 1
    @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*.2011-12-13
  • 2
    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.2011-12-13
  • 0
    @AndréNicolas: I agree (hence my query at the beginning... )2011-12-14
  • 0
    This is a great question for the idea that if you want a good answer you need to ask a precise question. Arturo Magidin has given a good answer to one reading of the question. If you don't like that, please explain why, which will likely be that the question is not the one he answered. Then somebody can answer the right question.2011-12-15
  • 0
    @ArturoMagidin - in your very first comment you sought a _valid_ clarification. You observed that "`numbers that are the product of exactly 3 distinct primes less than a 100` ... [is] `a bit trickier` [problem]". My question is about the **bit** bit. :) See http://math.stackexchange.com/questions/1733791/. I do not think it is trivial, esp as the number becomes much larger than 100.2017-04-06

1 Answers 1

5

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?

  • 0
    2300? not sure if correct.2011-12-13
  • 2
    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.2011-12-13
  • 0
    Using binomial coefficient 25C3 = 2300, its a tricky question.2011-12-13
  • 2
    @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.2011-12-13