翻开数学复习资料的 2.7 这节时很多人会被标题里的素数表、倒数数列、排列数弄懵——这三个东西看起来完全不搭界一个是数的分类表一个是分数求和一个是计数方式。但把它们放在同一节里恰恰是教材设计的高明之处因为做题时真正拉分的往往就是这三个知识点交叉出题的地方。这篇内容大概能帮你解决三件事第一素数表到底怎么快速生成而不是死记硬背第二倒数数列是怎么从越加越大变成精确求和的第三排列数什么时候用、什么时候千万别用。我会结合我实际给学生讲题时的经验和踩过的坑来写尽量让基础一般的读者也能直接上手。1. 素数表先分清判断素数和制造素数表两件事1.1 基本判定方法试除到根号n就够了素数也叫质数指大于 1 且只能被 1 和自身整除的自然数。注意大于 1这个前提因为 1 既不是素数也不是合数这是一切讨论的起点。判断一个数 n 是不是素数最朴素的方法是试除法用 2, 3, 4, 5, ... 依次去试除 n直到 n-1。但这样做效率太低而且没必要。关键结论是判断 n 是否为素数只需要试除到 √n 就够了。原因很简单。如果 n 是合数那么它一定能写成 n a × b其中 a 和 b 都是大于 1 的整数。这两个因数里必然有一个不大于另一个假设 a ≤ b那么 a 就不可能超过 √n。换句话说只要 n 在 2 到 √n 之间没有因数它就没有任何因数只能老老实实当素数。举个例子判断 97。√97 大约 9.8所以只需要用 2, 3, 5, 7 这四个素数试除。它们都不能整除 97因此 97 是素数。判断一个较大的数时这个结论能省下大量计算。比如 2023√2023 ≈ 44.9试除到 43 就可以。实际一算2023 7 × 289 7 × 17²所以它是合数。如果不懂只试除到根号 n这个原理你可能会傻傻除到 2022。1.2 筛法生成一张常用素数表是怎么手算出来的如果需要生成的是一段范围内的所有素数比如 1 到 200 的素数表挨个判断虽然可行但很慢。手算时代更聪明的办法叫埃拉托斯特尼筛法思路一句话把合数筛掉剩下的就是素数。具体步骤是这样的列出 1 到 200 的所有自然数先划掉 1。从 2 开始2 没被划掉是素数保留然后把 2 的所有倍数4, 6, 8, ...全部划掉。下一个没被划掉的数是 3保留然后划掉所有 3 的倍数9, 12, 15, ...。继续做处理 5、7、11、13……一直做到 √200 ≈ 14.1也就是处理到 13 就可以停了。表格里所有没被划掉的数就是 1 到 200 的全部素数。为什么筛到 √200 就能停因为如果某个合数 n ≤ 200它必然有一个不大于 √n 的质因数而 √n ≤ √200所以这个质因数一定被处理过了这个合数也一定被那一步划掉了。这不是巧合是必然。手工做表的技巧是把数字写成 10 列或 20 列这样同一列往往对应同一个个位数划倍数时规律非常明显。顺手给大家一个 100 以内的素数全集2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97一共 25 个。这张表我建议每个人都能亲手筛一遍而不是直接背。背下来的东西会忘亲手筛过之后你就理解了为什么 49 不在表里为什么 91 不在表里这类问题。1.3 素数表在题目里的两种典型用法用法一作为质因数分解和整除判断的武器库。遇到一个大数先拿小素数去试从 2、3、5 开始这是最常用也最可靠的路径。比如判断 20232、3、5 都不行到 7 就命中了。很多竞赛题和填空题就是考这个你手里有小素数表解题快得多。用法二利用素数表的直觉做逻辑推理。比如这一题两个素数之和为偶数这两个素数分别是什么如果你熟悉素数表会立刻意识到除了 2 以外所有素数都是奇数两个奇数相加必然是偶数而两个不同素数中如果有奇数加偶数和不可能是偶数。所以题目的潜台词是——其中一个必然是唯一的偶素数 2。这种表感只能靠对素数分布的熟悉来培养这也是老师为什么反复让你背 100 以内素数表的原因。2. 倒数数列从调和级数到裂项相消的完整链条2.1 倒数数列到底指什么倒数数列这个词指的不是某一个固定数列而是一类各项是由某个数列的项取倒数得到的。最常见的是 1, 1/2, 1/3, 1/4, ..., 1/n也就是每个正整数的倒数构成的数列也常称为调和数列。这个数列有两个反直觉的特点。第一它的每一项都在不断变小当 n 越来越大时1/n 无限接近 0但它永远不会等于 0。第二把它的前 n 项加起来结果会一直增长而且最终会超过任何给定的数——这就是调和级数发散。但发散的速度极其缓慢前 100 项和大约只有 5.19前 1000000 项和大约才 14.39。直观来说你需要累计满满一邮轮的倒数项才勉强让和数从 1 走到 15。这种每一项都在消失总和却不断积累的感觉是理解后续裂项求和的天然铺垫。除了 1/n广义的倒数数列还包括 1/(n(n1))、1/((2n-1)(2n1))、1/(n(n1)(n2)) 这类分母为多项式乘积的形式。它们的特点是形式上像分数却可以通过拆项变得极其规整。2.2 裂项相消最常用的求和处理处理倒数数列求和的看家本领是裂项相消。最基本的公式是1/[n(n1)] 1/n - 1/(n1)验证一下1/n - 1/(n1) (n1 - n)/[n(n1)] 1/[n(n1)]。为什么这个公式有用因为它把一项拆成了两项差当多个这样的项相加时每一项的后半部分会和后一项的前半部分抵消只剩下头和尾。举个例子求S 1/(1×2) 1/(2×3) 1/(3×4) ... 1/[n(n1)]用公式拆开S (1/1 - 1/2) (1/2 - 1/3) (1/3 - 1/4) ... (1/n - 1/(n1))中间的项全部抵消最终只剩下 S 1 - 1/(n1) n/(n1)。这个结果非常漂亮无论 n 多大和永远小于 1并且越来越接近 1。你可以把这一过程类比成多米诺骨牌中间每张牌推倒前后抵消只剩第一张和最后一张。再拓展开分母里两个因子的差不等于 1 时需要先补系数1/[n(nk)] (1/k) × (1/n - 1/(nk))比如 1/((2n-1)(2n1))差是 2所以拆成 (1/2)[1/(2n-1) - 1/(2n1)]。遇到分母是三项乘积时也可以裂1/[n(n1)(n2)] (1/2)[1/(n(n1)) - 1/((n1)(n2))]方法不变先把 1/[n(n1)(n2)] 看作两个大因子 1/[n(n1)] × 1/(n2) 或作整体拆分系数通过通分确认。这里我想强调一个实操经验很多学生裂项之后中间项看似抵消但会漏掉系数或写错符号。我的建议是拆完后随手写一个具体的数值检验比如令 n3看看等式两边相不相等。这个习惯能帮你避开几乎所有粗心错误。2.3 倒数和为什么和素数表沾边这部分算是知识的彩蛋倒数数列和素数表之间其实存在一条极漂亮的暗线。欧拉当年给出过这样一个结果全体正整数倒数和即调和级数可以展开成对所有素数的连乘积1 1/2 1/3 1/4 1/5 ... ∏_{p为素数} 1/(1 - 1/p)右边的每一个因子 1/(1 - 1/p) 对应一个等比级数求和1 1/p 1/p² 1/p³ ... 1/(1 - 1/p)把所有这些因子乘起来利用每个正整数都可以唯一分解成素数幂乘积这个算术基本定理展开后的每一项恰好对应一个 1/n。所以素数的分布和调和级数的发散直接挂上了钩左边是发散的右边的无穷乘积也必须发散从而反推出素数有无穷多个。你不需要记住这个证明的所有细节只需要感受到一件事素数表不是孤立的字典它和数列求和之间存在深刻的联系。这也是为什么教材会把它们放在同一个章节里引导你建立网状知识结构。3. 排列数公式背后最容易忽略的判定与边界3.1 排列数公式与速算排列数的定义是从 n 个不同元素中取出 m 个m ≤ n按照一定的顺序排成一列所有不同排列的个数记作 A(n, m) 或 P(n, m)。公式有两种表现形式A(n, m) n! / (n-m)! n × (n-1) × (n-2) × ... × (n-m1)第二种展开形式是最适合口算的从 n 开始连续往下乘 m 个数。比如 A(10, 3) 10 × 9 × 8 720三下五除二就出来了比先算 10! 再除以 7! 快得多。那 A(10, 4) 呢10 × 9 × 8 × 7 5040。记住这个口诀往下乘 m 次。我第一次给初学者教这个时大家特别喜欢把最后一项写成 n-m结果就错了。最后一项是 n-m1。为什么因为第一项是 n第 m 项自然就是 n-(m-1) n-m1。同时要注意一个约定0! 1。这保证了 A(n, n) n! / 0! n!也保证了组合数公式的对称性。虽然这个约定刚开始反直觉但它是整个排列组合体系自洽的前提。3.2 排列与组合的分水岭次序排列数和组合数只差一口气组合数 C(n, m) 计算的是选出来即可不考虑顺序排列数要求选出来之后还要安排顺序。数学上组合数等于排列数除以 m!C(n, m) A(n, m) / m! n! / [m! (n-m)!]为什么除以 m!因为选出的 m 个元素一旦确定它们还有 m! 种内部排列顺序而组合认为这些顺序都一样所以要全部除掉。我给学生讲时最喜欢用两个生活场景作对比从 5 个候选人中选 3 个人分别担任班长、副班长、学习委员这是排列问题因为职务不同同样的三个人换一下职位就变成另一种结果。从 5 个候选人中选 3 个人组成一个小组去参加活动这是组合问题因为小组内部怎么排顺序最后还是一组人。判断标准就一句话交换两个元素之后结果变了没有变了就是排列没变就是组合。很多同学一看到选字就直接套组合数这是大坑。比如题目里出现排成一行安排到三个不同岗位组成一个三位数这些都是典型的排列信号。3.3 排列数中必须注意的三类边界情况边界情况最容易拉开分差说三个高频点。第一m 0 和 m n 的情况。A(n, 0) 1表示一个都不取什么都不做只有一种做法。A(n, n) n!表示取出全部并排序这就是全排列。第二m n 的情况。公式里会出现负数的阶乘这在数学上没有定义所以 A(n, m) 当 m n 时直接视为 0。考试时遇到m n不要愣住答案是 0没有别的戏。第三元素中有重复时的去重逻辑。标准排列数基于n 个元素互不相同的前提。如果元素有重复比如 AABB 这四个字母全排列不能直接用 4!而要除以重复元素内部的排列数4! / (2! × 2!) 6。这是因为两个 A 互换位置在视觉上完全一样在标准排列中被重复计数了。还有一个容易忽略的变体是环形排列。n 个不同元素围成一圈排列数是 (n-1)!而不是 n!。因为把所有元素旋转一位在圆桌场景下是同一种坐法所以要除以 n 种旋转对称得到 (n-1)!。这种题只要在围成一圈四个字里见到就要立刻切换公式。4. 一道综合题把三个知识点串起来4.1 题目本身把前面三个主题放在一道题里才能真正检验你有没有学透。我设计了一道很典型的题目设集合 S {1, 2, 3, ..., 10}A 为 S 中所有素数组成的集合。(1) 写出 A 的所有元素并求 A 中所有元素的倒数和(2) 从 S 中取 3 个不同的数排成一列若这一列中至少含有一个 A 中的元素求排列总数。这道题第一问考素数表和倒数数列第二问考排列数加计数思想非常适合作为综合训练。4.2 完整解算过程先看第 (1) 问。S 里的素数也就是 1 到 10 的素数用 10 以内的素数表一对照就知道2, 3, 5, 7。所以 A {2, 3, 5, 7}共 4 个元素。倒数和1/2 1/3 1/5 1/7通分时2, 3, 5, 7 两两互质公分母是 2 × 3 × 5 × 7 210。1/2 105/2101/3 70/2101/5 42/2101/7 30/210。四项相加得 247/210这个分数已经不能再约分所以倒数和是 247/210。再看第 (2) 问。三个不同数排成一列全部可能的总数是 A(10, 3) 10 × 9 × 8 720。因为元素互不相同所以这是个标准排列数。题目要求至少含有一个素数。正面分类可以分三类恰好 1 个素数、恰好 2 个素数、恰好 3 个素数步骤多按正难则反的思路直接排除一个素数都没有的情况更方便。S 中非素数这里包含 1 和合数是 {1, 4, 6, 8, 9, 10}共 6 个。从这 6 个数中取 3 个排一列排列数是 A(6, 3) 6 × 5 × 4 120。所以满足要求的排列总数 720 - 120 600。4.3 换问法之后的陷阱变体这道题如果换个问法答案和做法都会完全不同。比如改成恰好含有 1 个素数。那么要先从 4 个素数里选 1 个从 6 个非素数里选 2 个再把这 3 个不同数字全排列C(4, 1) × C(6, 2) × 3! 4 × 15 × 6 360这里用到了组合数选元素加排列数排顺序的混合思路。再比如改成恰好含有 2 个素数C(4, 2) × C(6, 1) × 3! 6 × 6 × 6 216三种情况相加360 216 24 600恰好和至少一个的答案一致验证了我们反面算没有算错。还有一个更隐蔽的陷阱如果把排成一列改成组成一个集合题意就从排列变成组合答案变成C(10, 3) - C(6, 3) 120 - 20 100你会发现一旦次序不再是重点数值立刻缩水六倍。这也是为什么我一直强调审题时先看有没有顺序再看数字是什么。5. 用代码把三个主题全部验证一遍5.1 素数表生成两种写法对比我习惯在讲完手算方法后带着学生用 Python 验证。这里真的是两个世界互证的时刻。试除法版本非常适合理解定义import math def is_prime(n): if n 2: return False for d in range(2, int(math.sqrt(n)) 1): if n % d 0: return False return True primes [n for n in range(1, 101) if is_prime(n)] print(primes)输出结果就是前面列出的 25 个素数。筛法版本更能体现批量制造一张表的优势def sieve(n): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n ** 0.5) 1): if is_prime[i]: for j in range(i * i, n 1, i): is_prime[j] False return [i for i in range(n 1) if is_prime[i]] print(sieve(100))注意筛法里的优化内层循环从 i × i 开始而不是从 2 × i 开始。因为 i × 2, i × 3, ..., i × (i-1) 这些数早就在更小的素数处理时被划掉了没必要再划一遍。5.2 调和级数求和与前 n 项估算倒数数列对应到代码里最直观的验证就是算调和级数的前 n 项和。浮点版本import math n 1_000_000 s 0.0 for i in range(1, n 1): s 1 / i gamma 0.5772156649015329 print(s) # 约 14.392726 print(math.log(n) gamma) # 约 14.392726你会发现前一百万项和大约只有 14.39而且非常接近 ln(n) γ其中 γ 是欧拉常数。这个近似关系可以当常识记住很多数列放缩题都会用到它。如果想知道精确值比如前 100 项的和到底是多少用 Python 的 Fraction 模块可以避免浮点误差from fractions import Fraction n 100 s sum(Fraction(1, i) for i in range(1, n 1)) print(s)输出会是一个分子分母都很大的分数这正是倒数数列精确计算的完整表现。想让结果既精确又直观可以先转小数再看分数。5.3 排列数计算与结果校验排列数在 Python 里可以直接用 math.permimport math print(math.perm(10, 3)) # 720 print(math.perm(6, 3)) # 120 print(math.perm(10, 3) - math.perm(6, 3)) # 600如果不想依赖标准库自己写一个递推版也很简单def perm(n, m): res 1 for i in range(m): res * n - i return res这个函数和排列数公式 n × (n-1) × ... × (n-m1) 完全对应。当 n 较大时Python 的整数没有溢出问题但要注意如果 m 很大结果会爆炸式增长比如 perm(50, 25) 已经是一个天文数字这一点和倒数数列越来越慢形成鲜明对比。我把第四节那题用代码重新跑了一遍total perm(10, 3)no_prime perm(6, 3)total - no_prime 输出 600和手算结果一致。这种验证方式对面批学生特别有用一眼就能看出计算过程的哪个环节出了错。6. 这节内容的高频错误与我的实操体会6.1 一张高频错误对照表以下是这些年我在作业和考试里最常看到的错误整理成一张对照表方便你自查。错误场景错误做法正确做法根本原因判断素数把 1 当成素数1 既不是素数也不是合数对定义理解不到位判断素数试除到 n/2 甚至 n-1只需试除到 √n忽略了因数成对出现筛法生成素数表内层从 2i 开始划从 i×i 开始划没有意识到小倍数已被处理倒数数列求和1/(n(n2)) 直接拆成 1/n - 1/(n2)应为 (1/2)(1/n - 1/(n2))裂项系数漏算裂项相消中间项抵消后符号写反每拆一项先验证 n1 是否成立对相消依赖直觉没验证排列数计算A(n, m) 最后一项写成 n-m最后一项是 n-m1忽略了第 m 项的索引关系排列与组合选字必用组合数先判断交换元素后结果是否改变把场景信号当万能套用排列数边界出现 m n 时套公式强行算结果视为 0公式定义域没弄清综合计数正难却硬算用总数减去反面情况缺少正难则反的意识这里面最让我无奈的是裂项系数漏算和交换元素后没判断次序两处。因为它们不是不懂而是做题太快跳过了最基本的验证环节。6.2 几个真正帮到我的习惯最后聊几个实操体会也是我每次讲课都会反复强调的东西。第一个习惯裂项后立刻取个具体数值验算。拆完 1/[n(n2)]就顺手把 n3 代进去左边 1/15右边 (1/2)(1/3 - 1/5) (1/2)(2/15) 1/15对了再继续下一项。这个习惯用不了五秒钟却能拦住一半以上的计算失误。第二个习惯排列组合题先回答有没有顺序。我要求学生在草稿纸上把排列/组合这个判断明确写出来再动笔算公式。别小看这一步它能强制你过一遍脑子比任何口诀都有效。第三个习惯素数表不要只背 100 以内的还要熟悉 100 到 200 之间的常见素数。做题时常常遇到 127、139、149、151、157、163、167、173、179、181、191、193、197、199 这一串多混个脸熟判断题能省下大量试除时间。第四个习惯综合题算完一个结果一定要用另一种方法交叉验证。比如第四节那个至少一个素数我们既用了正面分类又用了反面扣除两个答案对上了才敢写最终结果。这个习惯放在任何数学章节里都成立——能自洽的结果通常才是真正可靠的结果。把素数表 倒数数列 排列数这三个板块连起来看你会发现它们都在训练同一种能力把一个表面复杂的问题拆解成一系列可以精确计算、精确判断的小步骤。这个过程熟练之后不光是数学考试任何需要细粒度分析的实际问题你都会比没练过的人更快找到抓手。
