How many positive integers less than 100 have exactly four odd factors but no even factors?
A. 14
B. 15
C. 16
D. 17
E. 18
Source: 800Score
A. 14
B. 15
C. 16
D. 17
E. 18
Source: 800Score
I actually get 19. If the question means 4 DIFFERENT odd factors, then I get 16.
I'm sure there's a more elegant solution, but I didn't see it right off the bat, so with a 2 minute limit in mind (this ended taking me around 2:30), I went about it like this:
- As with any number, two factors are going to be 1 and itself. Since we need EXACTLY four odd factors, we're looking for odd prime number pairings whose product is less than 100 (that is, we're looking for numbers N whose factors are {1, prime factor1, prime factor2, N}).
- If one of your prime factors is 3, then the second factor has to be less than 33. Include all the odd prime numbers up to 33 (this is where it helps to have memorized prime numbers). There are 10, including 3 itself (3, 5, 7, 11, 13, 17, 19, 23, 29, 31).
- If one of your prime factors is 5, then the second factor has to be less than 20. Include all the odd prime numbers up to 20, but exclude 3 because the {3,5} pairing has already been counted. There are 6, including 5 itself (5, 7, 11, 13, 17, 19).
- If one of your prime factors is 7, then the second factor has to be less than 14. Include all the odd prime numbers up to 14, but exclude 3 and 5 because the {3,7} and {5,7} pairing has already been counted. There are 3, including 7 itself (7, 11, 13).
- There aren't any other pairings to consider because the next prime number is 11, and 11*11 is greater than 100 (remember we've already counted {3,11}, {5,11} and {7,11}).
- 10+6+3 = 19. This obviously isn't among their answers, so I'm guessing they meant 4 DIFFERENT factors, in which case take out {1,3,3,9}, {1,5,5,25} and {1,7,7,49}.
