GESP 八级 · GESP 202406 C++ 八级 第 10 题

小于或等于给定正整数 $n$ 的数中，与 $n$ 互质的数的个数，我们称为欧拉函数，记作 $\phi(n)$。下面说法错误的是（ ）。

质数判定：检查2到√n即可。筛法：埃氏筛O(n log log n)，线性筛O(n)。注意1既不是质数也不是合数。

1不是质数也不是合数。埃氏筛法标记时从i×i开始而非从2×i开始，因为小于i×i的倍数已经被更小的质数筛过。

【考点】欧拉函数｜互质数判定｜素数性质

【考纲定位】GESP八级数论模块。命题人把 φ(n) 的定义塞进概念辨析题，不是考计算而是考"互质"这个核心概念——很多考生看到"相邻"就条件反射判定互质，却分不清"相邻整数"和"相邻素数"两种语境，导致选项 D 成为最大陷阱。

【解题思维】先锁定 φ(n) 定义：≤n 且与 n 互质的数。逐项验证：A 问素数 p，1,2,...,p−1 都小于 p 且与 p 没有公共因子>1，故 φ(p)=p−1，正确；B 两个不同素数 p≠q，公共因子只能是 1，必互质，正确；C 相邻整数 n,n+1，gcd(n,n+1)=gcd(n,1)=1，正确；D 说"相邻的两个素数不一定是互质数"，既然 B 已证任意两个不同素数必互质，D 的反例不存在，故错。

【陷阱拆解】D 选项的阴险之处在于偷换概念：把"相邻"从整数序关系偷换成素数列表序关系，制造"相邻素数可能不互质"的假象。命题人预判考生会背"相邻必互质"的结论，却忘了限定前提——相邻整数必互质，但相邻素数仍必互质（因为素数两两互质）。如果你只背"相邻互质"这个结论而不理解本质（gcd(n,n+1)=1 的证明），就会误判 D。

【反命题思维】若把 D 改成"相邻的两个整数一定是互质数"，则变正确；若把 D 改成"相邻的两个合数不一定是互质数"，则变正确（如 4 与 6）。刷到这类题先问自己：题干里的"相邻"到底指什么序？命题人想考我的是定义边界，不是结论记忆。