Question

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

Answer

Answer: 109

Concepts:factor counting prime combinations

Difficulty rating: 2070

Solution:

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

In the first case we need $p$ and $q$ both less than $50.$ There are $15$ primes below $50,$ giving $\binom{15}{2} = 105$ such numbers. In the second case we need $p^2 \lt 50,$ which holds for $p = 2, 3, 5, 7,$ giving $4$ more.

The total is $105 + 4 = 109.$

2005 AIME I Problem 3

Answer: 109

Difficulty rating: 2070

Solution:

Problem 3 in Other Years