2005 AIME I Problems/Problem 3

Revision as of 21:22, 27 November 2017 by Slackroadia (talk | contribs) (Solution)

Problem

How many positive integers have exactly three proper divisors (positive integral divisors excluding itself), each of which is less than 50?

Solution

Suppose $n$ is such an integer. Then one of its factors is $1$, so $n$ must be in the form $n=p\cdot q$ or $n=p^3$ for distinct prime numbers $p$ and $q$.

In the first case, the three proper divisors of $n$ are $1$, $p$ and $q$. Thus, we need to pick two prime numbers less than $50$. There are fifteen of these ($2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43$ and $47$) so there are ${15 \choose 2} =105$ numbers of the first type.

In the second case, the three proper divisors of $n$ are 1, $p$ and $p^2$. Thus we need to pick a prime number whose square is less than $50$. There are four of these ($2, 3, 5$ and $7$) and so four numbers of the second type.

Thus there are $105+4=\boxed{105}$ integers that meet the given conditions.

See also

2005 AIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 2
Followed by
Problem 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png