AMC12 2005 A

AMC12 2005 A · Q18

AMC12 2005 A · Q18. It mainly tests Inclusion–exclusion (basic), Primes & prime factorization.

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$?

称一个数为“质数样”数，如果它是合数但不被 $2$、$3$ 或 $5$ 整除。最小的三个质数样数是 $49$、$77$ 和 $91$。小于 $1000$ 的质数有 $168$ 个。小于 $1000$ 的质数样数有多少个？

(A) 100 100

(B) 102 102

(D) 106 106

(E) 108 108

Answer

Correct choice: (A)

正确答案：（A）

Solution

The given states that there are $168$ prime numbers less than $1000$, which is a fact we must somehow utilize. Since there seems to be no easy way to directly calculate the number of "prime-looking" numbers, we can apply complementary counting. We can split the numbers from $1$ to $1000$ into several groups: $\{1\},$ $\{\mathrm{numbers\ divisible\ by\ 2 = S_2}\},$ $\{\mathrm{numbers\ divisible\ by\ 3 = S_3}\},$ $\{\mathrm{numbers\ divisible\ by\ 5 = S_5}\}, \{\mathrm{primes\ not\ including\ 2,3,5}\},$ $\{\mathrm{prime-looking}\}$. Hence, the number of prime-looking numbers is $1000 - (168-3) - 1 - |S_2 \cup S_3 \cup S_5|$ (note that $2,3,5$ are primes). We can calculate $S_2 \cup S_3 \cup S_5$ using the Principle of Inclusion-Exclusion: (the values of $|S_2| \ldots$ and their intersections can be found quite easily) Substituting, we find that our answer is $1000 - 165 - 1 - 734 = 100 \Longrightarrow \mathrm{(A)}$.

题目给出小于 $1000$ 的质数有 $168$ 个，这是一个我们必须设法利用的事实。由于似乎没有直接计算“质数样”数个数的简便方法，我们可以用补集计数。我们可以把从 $1$ 到 $1000$ 的数分成若干组：$\{1\},$ $\{\mathrm{能被\ 2\ 整除的数}=S_2\},$ $\{\mathrm{能被\ 3\ 整除的数}=S_3\},$ $\{\mathrm{能被\ 5\ 整除的数}=S_5\}, \{\mathrm{不包括\ 2,3,5\ 的质数}\},$ $\{\mathrm{质数样数}\}$。因此，质数样数的个数为 $1000 - (168-3) - 1 - |S_2 \cup S_3 \cup S_5|$（注意 $2,3,5$ 是质数）。我们可以用容斥原理计算 $S_2 \cup S_3 \cup S_5$：（$|S_2| \ldots$ 及其交集的值都很容易求出）代入后可得答案为 $1000 - 165 - 1 - 734 = 100 \Longrightarrow \mathrm{(A)}$。

Topics