看到“2.7素数表倒数数列排列数”这个标题我第一反应是这八成是某本数学教材或者程序设计基础课里的一个小节。因为2.7这个编号通常意味着第二章已经讲完基本概念开始进入第一个能把知识点串起来的关口。你可能也经历过这种时刻——老师在黑板上列出一排素数让背下来然后在讲循环小数的课上突然问“1/7的循环节是多少”再过几节课又开始算排列数。表面上看这三块内容互不相干实际上它们都指向同一个底层问题整数之间的结构到底是什么。这篇文章我想带你一起把这三个概念拆开揉碎。不管你是正在准备考试的学生、刚学编程不久的开发者还是单纯对数字规律感兴趣的人按照这篇文章的节奏把表做出来、把代码跑一遍你会发现它们之间的联系比你想象中紧密得多。关键是每一步我给出的方法和经验都是我实际用过、也踩过坑之后整理出来的。1. 从“2.7”说起三个概念为什么总被放在一起1.1 一个章节编号透露的编排思路能出现在第二章第七节的内容通常有一个共同点它们都是“基础中的基础”。素数表是数论的基本工具倒数数列是实数和数论交叉的第一道观察窗排列数是离散数学和组合数学的起点。把这三个放在一个小节里其实是很多教材的常见做法原因很简单——它们都适合用“表格”来组织和观察规律。我当年第一次看到这个编号组合时以为老师是想凑课时后来自己动手把三张表都列了一遍才发现这种编排是有道理的。素数表告诉你哪些数“拆不开”倒数数列告诉你整数之间做除法会产生什么样的循环排列数告诉你从一堆东西里选出一排有多少种选法。这三个问题分别对应了数论、小数结构、计数原理三个方向而它们都用同一个工具来落地——列一张表找规律。1.2 三张“表”的共同底层逻辑很多人容易忽略这三个概念都在处理“有限与无限”的关系。素数表看起来是一张有限的表但素数本身是无限的倒数数列是无限项的数列但一个有理数的十进制展开最终必然进入循环也就是无限中嵌套着有限排列数在n固定的时候是有限的可一旦允许n变化就铺开成了阶乘序列这个无限延展的结构。正是“有限的表”和“无限的结构”之间的张力让它们值得被放在一起讲。实际操作中这种关系体现得更具体你要判断一个大数是不是素数可以用之前筛好的素数表去试除你要理解为什么1/7的循环节长度恰好是6需要借助模运算你要快速计算一个组合数又需要先准备好阶乘表。也就是说这三块内容不是三个孤岛而是同一片大陆上的三个高地。2. 素数表怎么把质数整整齐齐排出来2.1 朴素判定为什么只需要试除到根号n判断一个数n是不是素数最朴素的办法就是用2到n-1之间的所有整数去试除。但这个方法有一个明显的优化空间如果n是一个合数那么它一定能写成n a * b的形式其中a和b都大于1。a和b不可能同时大于根号n因为那样乘积就超过n了。所以最小那个因子一定不超过根号n。这意味着试除范围可以安全地缩小到2到根号n。举个例子判断101是不是素数只需要试除2、3、4、……、10如果能整除就不是素数否则就是。你不需要一直试到100。这个结论不仅是手算的省力技巧也是写代码时必须要注意的边界条件。很多初学编程的人在判断素数时会写成for i in range(2, n)这不算错但做了大量无用功写成range(2, int(n ** 0.5) 1)才是正确的姿势。2.2 埃拉托斯特尼筛法一张表的完整生成如果需要判断的数不是一两个而是一大批挨个试除就不够高效了。这时候用埃拉托斯特尼筛法也叫埃氏筛能一次性构造出一整张素数表。思路特别朴素就像在纸上列出2到N的所有整数然后从最小的素数2开始划掉它的倍数再找到下一个没被划掉的数3划掉3的倍数循环往复最后剩下的都是素数。写成Python代码最经典的版本是这样的def sieve(n): is_prime [True] * (n 1) if n 0: is_prime[0] False if n 1: 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(2, n 1) if is_prime[i]] print(sieve(100))运行之后你会在屏幕上得到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。注意内层循环里我特意从i * i开始而不是从2 * i开始。原因是比i * i小的i的倍数一定已经被更小的素数因子筛掉了从i * i起步能减少大量重复操作。如果你有兴趣可以自己对比一下两种写法的耗时差距。2.3 素数表到底能用来干什么有了素数表第一件能做的事就是快速分解质因数。比如给出一个数360我可以拿一张小素数表从2开始试除360除以2等于180再除以2等于90再除以2等于45然后换到345除以3等于15再除以3等于5最后5除以5等于1于是360 2^3 * 3^2 * 5。这个过程在手工计算时代靠的就是一本素数表。在现代编程里素数表同样常用。判断一个数的质因数分解就要先准备好素数表某些哈希表设计、随机算法、竞赛题里的数论问题也都要提前筛出素数。甚至在教学场景一张打印好的素数表贴在笔记本扉页是很多数学系学生的传统操作。我自己当年就干过这事现在回头看那不只是心理安慰确实能加快手算分解的速度。3. 倒数数列循环小数里藏着的结构3.1 倒数数列与调和级数的边界倒数数列指的是1/1, 1/2, 1/3, 1/4, 1/5, …… 这样排列下去。它的每一项都在变小趋向于0但要注意一个反直觉的事实这些项全部加起来并不收敛于某个有限值而是会一直增大下去。这就是著名的调和级数发散。证明方法有很多最直观的是分块放缩把1/3到1/4这四项加起来每项都大于等于1/4所以这一块的和大于等于1/2再把1/5到1/8这四项加起来也都大于等于1/8又得到1/2继续这样分块下去每一块的和都至少是1/2所以总和可以超过任意大的数。这个结论第一次看到的时候我是不太相信的因为直觉上各项都在往0走总和却不受控制。也正是这种反直觉让倒数数列成了理解“无限求和”的绝佳入门材料。3.2 长除法看循环节生成对非数学专业的人来说倒数数列里更有趣的是它的小数展开。拿1/7来说我们知道它等于0.142857 142857……循环节是142857。为什么恰好是这六位用手工长除法就能看出来。1除以7商0余1把余数1乘以10得到10除以7商1余3把余数3乘以10得到30除以7商4余2余数2乘以10是20除以7商2余6余数6乘以10是60除以7商8余4余数4乘以10是40除以7商5余5余数5乘以10是50除以7商7余1。这一步余数又变回1正好和最开始余数一样所以接下来的商必然重复前面六个数字循环节长度是6。这个观察特别重要小数展开是否循环、循环在哪里开始、循环节多长完全由每次除法之后的余数决定。一旦某个余数重复出现整个循环就锁定了。换句话说循环小数的循环节生成问题本质上是一个“余数轨迹”的问题而余数又是整数它只能在0到分母减1之间取值所以循环必然发生且循环节长度不可能超过分母减1。3.3 循环节长度与分母的关系如果分母是一个与10互质的正整数m那么1/m的循环节长度正好是满足10^k ≡ 1 (mod m)的最小正整数k。这里的含义是小数部分每经过k位余数就回到1于是商也回到最初的位置。用模运算的语言说这个最小的k就是10在模m乘法群里的阶。举个例子m7时10^1≡310^2≡210^3≡610^4≡410^5≡510^6≡1所以阶是6循环节长度就是6。如果分母含有因子2或5情形会复杂一些小数点后会出现一段不循环的部分。比如1/60.1666……因为6包含因子2所以首位商1之后从第二位开始的余数才进入循环。这一块细究起来还能写出一个统一的公式不过对初学者来说先掌握“余数重复导致循环”这个核心就已经足够。4. 排列数阶乘、连乘与边界条件4.1 排列数的定义和常用计算方式排列数解决的是这样一类问题从n个不同的对象中按顺序选出m个一共有多少种方案。记作A(n, m)也有的教材写作P(n, m)公式是A(n, m) n! / (n - m)!比如A(10, 3)就是从10个不同的人里选3个人排成一排第一个位置有10种选法第二个位置剩9种第三个位置剩8种所以总数是10 * 9 * 8 720。你会发现这个连乘形式比直接套阶乘公式直观得多口算心算都更方便。4.2 生成阶乘表的工程细节如果需要计算很多不同的排列数最经济的方式是提前把阶乘表算出来。阶乘表就是一张记录0!、1!、2!、3!……一直到N!的表。工程上有个很容易忽视的点阶乘增长极快20!已经是2432902008176640000约等于2.43乘以10的18次方超出了很多编程语言中32位整数甚至64位整数的舒适区。在Python里因为有大整数支持直接算不太容易溢出但在C、C、Java这些语言中就需要考虑用long long或者提前判断是否超出范围。一个实用的技巧是如果你知道后面的计算要在模某个大质数P下进行那么阶乘表可以一路取模存的是每个阶乘对P取模之后的结果这样内存占用和数值范围都可控。4.3 一个容易翻车的边界0! 与 m n排列数的问题里有两个高频边界坑。第一个是0!等于1这一点必须牢记因为A(n, 0)表示从n个对象中选0个并排成一列只有一种做法那就是什么都不做。第二个是当m n时排列数是0因为不可能从n个对象里取出比n还多个元素并保证不重复。写代码的时候我建议直接在最前面加一句判断if m 0 or m n: return 0。这句话可以省去后面一堆边界判断的麻烦。很多人写完排列数函数测试到一半发现负索引或者越界往往就是漏了这条。还有一点m和n都必须是整数这在真实业务代码里看似显然但一旦输入来自外部接口还是得主动校验一下。5. 三张表串起来一个综合案例5.1 用素数表解读倒数数列的循环节现在把前面两张表连起来看。给定一个大整数m想知道1/m的小数展开循环节特征可以先对m做质因数分解分解过程就要用到素数表。分解出结果之后如果m只含2和5的因子那么1/m是有限小数如果m的因子里有其他素数那小数展开一定会进入循环。更进一步循环节的长度是由与10互质的那部分因子决定的通常需要对这部分因子分别计算10的阶然后取最小公倍数。比如m21分解成3 * 710模7的阶是610模3的阶是1那么1/21循环节长度就是lcm(1, 6)6。你可以自己长除法验证一下1/210.047619047619……循环节确实是047619。这就把“素数表”和“倒数数列”两张表变成了一条完整的推理链先查表分解再按模运算推循环节长度。5.2 n!中的素因子勒让德公式排列数离不开阶乘而阶乘的质因数分解有很好的结构。要计算n!里素数p出现的次数不需要把n!真的算出来直接用勒让德公式v_p(n!) floor(n / p) floor(n / p^2) floor(n / p^3) ...直到某一项变成0为止。这个公式的意思是从1到n的所有整数里每p个数就有一个含因子p每p^2个数就有一个含p^2以此类推。举个例子10!里因子2的个数是floor(10/2) floor(10/4) floor(10/8) 5 2 1 8。所以10! 2^8 * 3^4 * 5^2 * 7。这个公式在实际中很常用尤其是处理超大阶乘的组合数问题时你可以不经过乘除法就精确知道某个素数在结果里的指数。这里用的素数表是整个推理的前提没有素数表你连要查哪些p都不知道。5.3 组合数大数取模把三张表变成一套代码组合数C(n, m)和排列数的关系是C(n, m) A(n, m) / m!它也是从n个对象中选m个但不计较顺序。如果n和m很大直接算阶乘再相除会溢出通常的做法是在一个素数模数下计算。这里把前面几张表全部用上先筛出素数选一个足够大的素数MOD比如竞赛中常用的1000000007然后预处理阶乘表和逆元表最后用乘法逆元代替除法。MOD 10 ** 9 7 N 100 fact [1] * (N 1) for i in range(1, N 1): fact[i] fact[i - 1] * i % MOD inv_fact [1] * (N 1) inv_fact[N] pow(fact[N], MOD - 2, MOD) for i in range(N, 0, -1): inv_fact[i - 1] inv_fact[i] * i % MOD def comb(n, m): if m 0 or m n: return 0 return fact[n] * inv_fact[m] % MOD * inv_fact[n - m] % MOD print(comb(100, 50))这里的核心逻辑是当MOD是素数时根据费马小定理a的MOD-2次方就是a的逆元也就是“模意义下的倒数”。你没看错这就是倒数数列在离散数学里的投影一个数的倒数不再是小数而是另一个整数使得模乘法等于1。6. 常见问题与避坑实录6.1 素数判定里的边界陷阱实测下来素数判定最容易踩的坑有三个。第一个是忘记处理2这个特例2是唯一的偶素数如果你从2开始循环就没事但很多人习惯写if n % 2 0: return False却忘了n2也满足这个条件直接被误判成非素数。第二个是忘记1既不是素数也不是合数很多初学者写完代码发现sieve(1)返回了[1]就是因为初始标记没做对。第三个是试除范围写错写成range(2, int(n ** 0.5))会漏掉平方数这个边界比如判断9时根号9等于3range(2, 3)只试了2没有试3就会误判9是素数。正确的写法应该是int(n ** 0.5) 1。6.2 循环节计算千万别用浮点数不少人在算1/7的循环节时第一反应是用1除以7得到一个浮点数然后从小数部分找重复串。这个思路非常容易翻车因为浮点数在计算机里的精度有限1/7这样的循环小数根本不能被精确表示你看到的0.142857后面可能还有一大堆误差尾巴找循环节会错得非常隐蔽。正确的做法是用整数长除法模拟手算过程只记录每一步的商和余数当余数重复出现时循环节就确定了。6.3 排列数溢出与取模误区排列数计算另一个高频问题是大数溢出。用C或者Java时计算20!就接近long long的上限了这时候如果继续算更大的排列数结果会变成负数或者被截断且很难排查。应对思路有三种换Python这种支持大整数的语言使用组合数递推公式C(n, m) C(n-1, m-1) C(n-1, m)来避免直接乘阶乘或者全程在模数下计算并把每一步乘法都取模。这里还要提醒取模看似简单却有一个隐蔽坑如果你用负数结果取模在某些语言里会得到负数。比如-3 % 1000000007在Python里结果是1000000004因为Python对模运算的定义偏向保证非负但在C语言里结果可能是-3。所以跨语言迁移代码时一定要在取模之后判断并修正为非负值。6.4 一点实操体会我强烈建议你亲手把这三张表都各自列一遍。不是用电脑而是用纸笔。列一张100以内的素数表用长除法写出几个分数的小数展开再手算几组排列数做完之后你对这些概念的理解深度会比刷十道题都管用。写在最后的经验做了这么多年数据处理和算法相关的工作我越来越觉得数学基础里最厉害的工具往往不是那些高深定理而是这种朴素的“先列表、再找规律”的思维模式。素数表、倒数数列、排列数三张表看起来都简单到不值得一提但它们组合起来能解决的实际问题远超预期。比如我自己在处理一些复杂订单组合计算时最后化简出来的核心还是一个排列数和组合数的取模运算在做数据抽样设计时也经常需要快速知道一个数能否被某个素数整除。这些东西听起来很基础但真到用的时候你会感谢当年认真列过表、认真写过筛法代码的自己。