2005 AMC 12A 第 18 题

Question

称一个数为“看似质数”，如果它是合数但不能被

2

，

3

和

5

整除。最小的三个看似质数是

49

，

77

和

91

。小于

1000

的质数有

168

个。小于

1000

的看似质数有多少个？

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

答案：A

知识点：容斥原理质数区间内整数计数

难度评级：1950

小提示：

用容斥原理数出小于

1000

且能被

2, 3

和

5

中至少一个整除的数。

Use inclusion-exclusion to count the numbers below

1000

divisible by

2, 3,

or

5

大提示：

从与

2, 3, 5

都互质的数中，去掉质数和数字

1

。

From the numbers coprime to

2, 3, 5,

remove the primes and the number

1

解答：

在

1

到

999

这

999

个数中，由容斥原理可得

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

个数能被

2, 3

或

5

中至少一个整除。

因此与

2, 3, 5

都互质的数共有

999 - 733 = 266

个；其中有

165

个质数（

168

个质数去掉

2, 3, 5

），另有

1

既不是质数也不是合数。

剩下

266 - 165 - 1 = 100

个就是看似质数。

所以正确答案是 A。

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.

2005 AMC 12A 第 18 题

答案：A

难度评级：1950

小提示：

大提示：

解答：

其他年份的第 18 题