欧拉函数详解：定义、性质与代码实现教程

一、教程目标

本教程将帮助你完成三件事：第一，准确理解欧拉函数φ(n)的数学定义及其与“互质”概念的关系；第二，掌握欧拉函数的三条核心性质（质数性质、质数幂性质、积性性质），并推导出适用于任意正整数的通用计算公式；第三，能够根据数据规模选择合适算法，用代码正确、高效地计算欧拉函数，并对结果进行多角度验证。

适合阅读对象：正在学习数论与算法的开发者、需要处理同余与互质相关计算的技术人员、接触公钥密码体制相关开发的工程师（其密钥生成阶段依赖与欧拉函数同源的运算），以及希望夯实数学基础的学习者。

二、适用场景

1. 算法与竞赛编程：求解互质计数、同余方程个数等数论问题。
2. 密码学开发：公钥加密方案在生成密钥时需要计算与欧拉函数密切相关的数值。
3. 工程计算：分数化简、周期判断、采样间隔选取等需要互质关系的场景。
4. 抽象代数学习：欧拉函数的值等于“模n乘法群”的阶，即所有不大于n且与n互质的数在模n乘法运算下构成一个群，其元素个数正是φ(n)。理解这一点有助于从群论视角把握同余结构。

三、前置准备

1. 数学基础：理解质数（大于1且只有1和自身两个因数的整数）、互质（两数最大公约数为1）、质因数分解（把n写成若干质数幂的乘积）等概念；了解同余记号更佳。
2. 编程基础：熟悉任一主流语言中的变量、循环、条件与函数封装即可。本文示例采用通用伪代码风格，可直接迁移到你熟悉的语言环境。
3. 验证环境：准备一个可运行脚本的计算环境（本地或任一通用开发环境均可），用于跑通示例并验证结果；手工验算阶段准备计算器即可。

四、实施步骤：从定义到通项公式

步骤一：吃透定义——φ(n)到底在数什么

欧拉函数（Euler’s totient function），记作φ(n)，表示不大于n的正整数中与n互质的数的个数，由瑞士数学家莱昂哈德·欧拉提出，因此也称欧拉φ函数或phi函数。

先看几个小例子建立直观感受：

• φ(1) = 1：约定1与自身互质，故取1；
• φ(8) = 4：不大于8的正整数中，1、3、5、7与8互质，共4个；
• φ(12) = 4：1、5、7、11与12互质，共4个。

注意“不大于n”这一边界：当n>1时，n与自身不互质，所以“不大于n”与“小于n”两种说法在计数结果上一致，但严谨实现中要写明循环范围，避免边界争议。

步骤二：掌握质数性质——φ(p) = p - 1

若p是质数，则1, 2, …, p-1中任何数都无法与p共享大于1的公因数，因此这p-1个数全部与p互质，即φ(p) = p - 1。例如φ(7)=6、φ(11)=10。这条性质也可作为程序实现的校验点：对任意质数p，程序算出的φ(p)必须等于p-1。

步骤三：掌握质数幂性质——φ(p^k) = p^k - p^(k-1)

对形如n = p^k的数（p为质数、k为正整数），“与n不互质”的数恰是p的倍数，在1到p^k内共有p^(k-1)个。用总数减去不互质的个数，得：

φ(p^k) = p^k - p^(k-1) = (p - 1)·p^(k-1)

例如φ(8) = φ(2^3) = 8 - 4 = 4，与步骤一的枚举一致；φ(9) = 9 - 3 = 6（即1、2、4、5、7、8）。

步骤四：掌握积性性质——互质时可拆分相乘

若m与n互质，则φ(mn) = φ(m)·φ(n)，这条性质称为“积性”，是欧拉函数最重要的结构性质。直观理解：由于m、n互质，“一个数与mn互质”等价于“它同时与m互质且与n互质”；借助中国剩余定理的思想，模mn的剩余类与“模m、模n剩余类的组合”一一对应，互质组合的个数自然相乘。

务必注意适用条件：仅当gcd(m, n)=1时才能拆分。反例：φ(4)=2，而φ(2)·φ(2)=1，两者不等，因为2与2不互质。这是初学者最容易踩的坑。

步骤五：汇总得到通用计算公式

将n做质因数分解：n = p1^a1 × p2^a2 × … × pk^ak。不同质数的幂之间两两互质，可对整体应用积性性质，再对每一项应用步骤三，得到：

φ(n) = ∏ (pi^ai - pi^(ai-1)) = ∏ pi^(ai-1) × (pi - 1)

等价写法：φ(n) = n × ∏ (1 - 1/pi)，连乘遍历n的所有互异质因数。

验算示例：n = 12 = 2^2 × 3，φ(12) = (4-2) × (3-1) = 2 × 2 = 4 ✓；n = 100 = 2^2 × 5^2，φ(100) = (4-2) × (25-5) = 2 × 20 = 40 ✓。

至此，“给定任意n如何求φ(n)”在数学上已有完整答案，接下来解决“如何用代码算”。

五、代码实现：三种方法与选型策略

方法一：暴力枚举法（单次计算、n较小时首选）

function phi_brute(n):
    count ← 0
    for i from 1 to n:
        if gcd(i, n) = 1:
            count ← count + 1
    return count

做什么：逐个检查1到n中每个数与n的最大公约数是否为1。为什么这样做：完全贴合定义，逻辑最简单、最不易出错。注意什么：时间复杂度约O(n·log n)，n达到千万级别时明显吃力，只适合小规模或一次性验证场景。

方法二：公式法（单次计算、n较大时首选）

function phi_formula(n):
    result ← n
    p ← 2
    while p × p ≤ n:
        if n mod p = 0:
            while n mod p = 0:
                n ← n / p
            result ← result - result / p
        p ← p + 1
    if n > 1:
        result ← result - result / n
    return result

做什么：在O(√n)内完成质因数分解，并同步按公式n·∏(1-1/p)累乘结果。为什么这样做：每找到一个质因数p，就从result中扣除p的份数（”result - result/p”即”result × (1-1/p)”的整数写法），处理完全部质因数即得答案。注意什么：其一，必须先算result/p再从result中减去，且用整数除法（由于p此时必为result的因数，除法是精确的），顺序颠倒会出错；其二，循环只查到√n，结束后若剩余的n仍大于1，说明它是一个大于√原值的大质因数，必须补扣一次，遗漏该分支是常见错误；其三，全程用整数运算，避免浮点形式的(1-1/p)引入精度误差。

方法三：线性筛（需批量计算φ(1)到φ(N)时首选）

function phi_sieve(N):
    phi[1] ← 1
    primes ← 空列表
    for i from 2 to N:
        if i 未被标记:
            将 i 加入 primes
            phi[i] ← i - 1
        for 每个质数 p in primes 且 i × p ≤ N:
            标记 i × p
            if i mod p = 0:
                phi[i × p] ← phi[i] × p
                break
            else:
                phi[i × p] ← phi[i] × (p - 1)
    return phi

做什么：在O(N)时间内求出1到N中每个数的欧拉函数值。为什么这样做：线性筛保证每个合数只被“最小质因数×某数”标记一次。设当前数为i、枚举到的质数为p：若p整除i，则i×p与i的质因数集合相同，相当于把i中p的指数加一，套用(p-1)p^(k-1)的递推得φ(i×p) = φ(i) × p；若p不整除i，则i与p互质，直接套积性性质得φ(i×p) = φ(i) × (p-1)。注意什么：数组大小要开到N+1；phi[1]必须初始化为1；内层循环要在i×p超过N时立即终止；p整除i时的break不能漏，否则复杂度退化。

选型速查：单次查询且n较小，方法一、二皆可；单次查询且n较大（如n在10^9量级），用方法二；批量查询多个n且上界N固定，用方法三预处理，之后每次询问O(1)读表。

六、结果验证

代码写完后，建议按四个层次验证，全部通过再投入使用。

1. 已知值抽查：φ(1)=1、φ(2)=1、φ(10)=4、φ(36)=12、φ(100)=40，程序输出与这些标准答案一致是最低门槛。
2. 性质回归校验：随机取多组互质的(m, n)，验证φ(mn)=φ(m)·φ(n)；取质数p验证φ(p)=p-1；取质数幂p^k验证φ(p^k)=(p-1)·p^(k-1)。任一不满足即说明实现有缺陷。
3. 方法间交叉比对：让方法一（可信但慢）与小范围运行的方法二、方法三逐一对拍，例如在1 ≤ n ≤ 1000内结果完全一致，可显著提升信心。
4. 恒等式校验：利用经典恒等式“n的所有因数d的φ(d)之和等于n”做整体校验。例如n=10，因数为1、2、5、10，φ(1)+φ(2)+φ(5)+φ(10) = 1+1+4+4 = 10 ✓。

七、常见问题与排查

问题1：结果差1或差某个因数比例。原因：方法二中”result - result/p”运算顺序写反，或遗漏循环结束后n > 1的大质因数分支。解决：在纸上手动模拟n=12的执行过程逐步核对result变化，重点检查整数除法先后顺序。

问题2：对不互质的数误用积性公式，结果偏小。原因：误以为φ(mn)=φ(m)φ(n)无条件成立，例如φ(4)≠φ(2)·φ(2)。解决：先对n做完整质因数分解，再逐项按质数幂计算；只有确认gcd(m,n)=1才可拆分。

问题3：暴力法在大n下超时。原因：方法一复杂度随n线性增长，属预期行为而非缺陷。解决：单次大n改用O(√n)的公式法；多次询问且上界固定时用线性筛预处理。

问题4：筛法结果错位或数组越界。原因：phi数组下标管理不当、内层循环未在i×p>N时及时终止、或phi[1]未初始化。解决：确认数组大小为N+1；循环内先判断上界再访问i×p；单独设置并自查phi[1]=1。

问题5：用浮点实现n·∏(1-1/p)时偶尔差1。原因：(1-1/p)无法被浮点精确表示，连乘后误差放大。解决：改用整数写法”result ← result / p × (p-1)”，先除后乘（此时p必为result的因数，除法精确），彻底规避浮点误差。

八、优化建议

1. 性能维度：按“单次O(√n)公式法、批量O(N)线性筛”的策略匹配场景，高频查询场景务必预处理后O(1)应答；筛法中i×p的下标计算在N较大时注意使用足够宽的整型承接。
2. 精度维度：所有实现坚持整数运算；若语言原生整数范围不足，选择支持大整数的运算环境，避免中间量溢出。
3. 可维护性维度：将欧拉函数计算封装为独立函数，与gcd等工具函数解耦；把第六节的验证清单直接转化为测试用例，保证后续重构不引入回归。
4. 稳健性维度：对输入做合法性校验（n须为正整数），n=1时返回约定值1；对外部提交的批量任务设置规模上限，防止极端参数拖垮计算服务。
5. 扩展维度：掌握欧拉函数后，可继续学习欧拉定理（若gcd(a,n)=1，则a^φ(n) ≡ 1 (mod n)），它是模幂快速运算与密码学计算的基础工具；欧拉函数也是积性函数的代表，线性筛思想可推广到大多数积性函数的批量求解。

九、总结

本教程从欧拉函数“数互质个数”的定义出发，依次建立了质数性质φ(p)=p-1、质数幂性质φ(p^k)=(p-1)·p^(k-1)与积性性质φ(mn)=φ(m)·φ(n)（要求m、n互质），并汇总为通用公式φ(n)=n·∏(1-1/p)；在实现层面给出了暴力枚举、公式分解与线性筛三种方法及各自的适用边界，最后提供了四层验证手段与五类常见问题的排查思路。掌握欧拉函数不仅是数论学习的关键一步，也为理解模n乘法群的结构、深入学习同余理论与公钥密码体制打下基础。建议读者在跑通三种实现后，继续向欧拉定理、积性函数筛法等方向延伸学习。