Difference between revisions of "2005 AIME I Problems/Problem 3"

m (+bxo)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
How many [[positive integer]]s have exactly three [[proper divisor]]s, each of which is less than 50?
+
How many [[positive integer]]s have exactly three [[proper divisor]]s (positive integral [[divisor]]s excluding itself), each of which is less than 50?
  
 
== Solution ==
 
== Solution ==
Line 12: Line 12:
  
 
== See also ==
 
== See also ==
* [[2005 AIME I Problems/Problem 2 | Previous problem]]
 
* [[2005 AIME I Problems/Problem 4 | Next problem]]
 
* [[2005 AIME I Problems]]
 
 
* [[Divisor_function#Demonstration | Counting divisors of positive integers]]
 
* [[Divisor_function#Demonstration | Counting divisors of positive integers]]
 +
{{AIME box|year=2005|n=I|num-b=2|num-a=4}}
 +
 
[[Category:Introductory Number Theory Problems]]
 
[[Category:Introductory Number Theory Problems]]

Revision as of 15:20, 4 March 2007

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 $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=109$ 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