Problem Solving

BTGmoderatorDC wrote:A positive integer is called semiprime if it is the product of exactly two not-necessarily-distinct prime numbers. A positive integer is called highly composite if it has more factors than any smaller positive integer has. How many positive integers are both semiprime and highly composite?

A. 0
B. 1
C. 2
D. 3
E. Infinitely many

OA C

Source: Veritas Prep

Let's first try to list down Semiprimes.

We are given that "A positive integer is called semiprime if it is the product of exactly two not-necessarily-distinct prime numbers."

Few Semiprimes are:

1. 4: We see that 4 = 2*2; product of exactly two primes
2. 6: We see that 6 = 2*3; product of exactly two primes
3. 9: We see that 9 = 3*3; product of exactly two primes
4. 10: We see that 10 = 2*5; product of exactly two primes

We can deduce that there would be infinitely many such numbers.

Note that 2, 3, 5, 7, 8 are not semiprime since

1. 2 = 1*2; Not a product of exactly two primes
2. 3 = 1*3; Not a product of exactly two primes
3. 5 = 1*5; Not a product of exactly two primes
4. 8 = 2*2*2; Not a product of exactly two primes

Let's first try to list down highly composite numbers.

We are given that "A positive integer is called highly composite if it has more factors than any smaller positive integer has."

Few highly composite numbers are:

1. 4: The factors of 4 are 1, 2, & 4; there are 3 factors. Since the number of factors of smaller positive integers 2 and 3 is 2 each (less than 3), number 4 is a highly composite number.

Since 4 is also semiprime, we can count this in our answer.

2. 6: The factors of 6 are 1, 2, 3 & 6; there are 4 factors. Since the number of factors of smaller positive integers 2, 3, 4, and 5 is 2 or 3 (less than 4), number 6 is also a highly composite number.

Since 6 is also semiprime, we can count this in our answer.

We must try for 9 and 10 since they are semiprimes. 9 is not a highly composite number since the number of factors of 9 is 3 (1, 3, and 9) and the number of factors of smaller number 8 is 4 (1, 2, 4, and 8) -- not greater than 4. The same goes with 10. We must stop here since subsequent compositive numbers will not have a greater number of factors than the number of factors of any of the smaller positive numbers.

Thus, there are only two semiprime and highly composite numbers: 4 and 6.

The correct answer: C

Hope this helps!

-Jay
_________________
Manhattan Review GMAT Prep

Locations: New York | Paris | Shanghai | Munich | and many more...

Schedule your free consultation with an experienced GMAT Prep Advisor! Click here.