2005 AMC 12A Problem 18

Question

Call a number “prime-looking” if it is composite but not divisible by

2,

3,

or

5.

The three smallest prime-looking numbers are

49,

77,

and

91.

There are

168

prime numbers less than

1000.

How many prime-looking numbers are there less than

1000?

100

102

104

106

108

Use inclusion-exclusion to count the numbers below

1000

divisible by

2, 3,

or

5

From the numbers coprime to

2, 3, 5,

remove the primes and the number

1

Among the

999

numbers from

1

to

999,

inclusion-exclusion gives

\begin{aligned} &499 + 333 + 199 - 166 \\ &\quad {}- 99 - 66 + 33 = 733 \end{aligned}

that are divisible by

2, 3,

or

5.

That leaves

999 - 733 = 266

numbers coprime to

2, 3, 5.

Of these,

165

are primes (the

168

primes minus

2, 3, 5

), and

1

is neither prime nor composite.

The remaining

266 - 165 - 1 = 100

numbers are prime-looking.

Thus, the correct answer is A.

Problem 18 in other years