2005 AIME I Problem 3

Attempt Problem 3 of the 2005 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2005 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

3.

How many positive integers have exactly three proper divisors, each of which is less than 50?50? (A proper divisor of a positive integer nn is a positive integer divisor of nn other than nn itself.)

Answer: 109
Concepts:factor countingprimecombinations
Difficulty rating: 2070
Small Hint:

A number has exactly four divisors in all — hence three proper ones — exactly when it is pqpq for distinct primes pp and q,q, or a prime cube p3p^3

Big Hint:

Count pairs of distinct primes less than 50,50, then add the primes pp with p2<50p^2 \lt 50

Solution:

An integer with exactly three proper divisors has exactly four divisors in total, so it is either n=pqn = pq with pp and qq distinct primes (proper divisors 1,1, p,p, qq) or n=p3n = p^3 with pp prime (proper divisors 1,1, p,p, p2p^2).

In the first case we need pp and qq both less than 50.50. There are 1515 primes below 50,50, giving (152)=105\binom{15}{2} = 105 such numbers. In the second case we need p2<50,p^2 \lt 50, which holds for p=2,p = 2, 3,3, 5,5, 7,7, giving 44 more.

The total is 105+4=109.105 + 4 = 109.

Problem 2#2
Full Exam

Problem 3 in Other Years