每日算法 — 使用java实现欧拉函数：线性筛构造与积性函数性质

算法背景

欧拉函数（Euler’s Totient Function），记作 φ(n)，表示小于等于 n 的正整数中与 n 互质的数的个数。例如 φ(1)=1，φ(6)=2（1和5与6互质）。欧拉函数在数论、密码学和组合数学中有着广泛的应用，如RSA加密算法就依赖欧拉定理。

欧拉函数具有积性函数的重要性质：若 gcd(a,b)=1，则 φ(ab)=φ(a)·φ(b)。利用这一性质，我们可以在线性筛素数的同时，高效计算出每个数的欧拉函数值。

核心公式

• 若 p 为素数，则 φ(p) = p - 1
• 若 p 为素数，k ≥ 1，则 φ(p^k) = p^k - p^(k-1) = p^(k-1)·(p-1)
• 积性性质：gcd(a,b)=1 ⇒ φ(ab) = φ(a)·φ(b)

Java实现

import java.util.Arrays;

/**
 * 欧拉函数线性筛实现
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 */
public class EulerTotient {

    // 存储每个数的欧拉函数值
    private int[] phi;
    // 标记是否为素数
    private boolean[] isPrime;
    // 存储筛出的素数
    private int[] primes;
    private int primeCount;

    /**
     * 构造函数，计算1到n所有数的欧拉函数值
     */
    public EulerTotient(int n) {
        phi = new int[n + 1];
        isPrime = new boolean[n + 1];
        primes = new int[n + 1];
        primeCount = 0;

        // 初始化
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        phi[1] = 1; // 1与自身互质

        // 线性筛核心
        for (int i = 2; i <= n; i++) {
            // 若i是素数，则φ(i) = i - 1
            if (isPrime[i]) {
                primes[primeCount++] = i;
                phi[i] = i - 1;
            }

            // 用当前素数去筛合数
            for (int j = 0; j < primeCount && i * primes[j] <= n; j++) {
                isPrime[i * primes[j]] = false;

                if (i % primes[j] == 0) {
                    // primes[j]是i的最小质因子
                    // φ(i * p) = φ(i) * p，当p整除i时
                    phi[i * primes[j]] = phi[i] * primes[j];
                    break;
                } else {
                    // primes[j]与i互质，利用积性性质
                    // φ(i * p) = φ(i) * φ(p) = φ(i) * (p - 1)
                    phi[i * primes[j]] = phi[i] * (primes[j] - 1);
                }
            }
        }
    }

    /**
     * 获取x的欧拉函数值
     */
    public int getPhi(int x) {
        if (x < 1 || x >= phi.length) {
            throw new IllegalArgumentException("超出范围");
        }
        return phi[x];
    }

    /**
     * 获取1到n所有数的欧拉函数值数组
     */
    public int[] getAllPhi() {
        return phi.clone();
    }

    /**
     * 单个数欧拉函数值计算（大数时使用，时间复杂度O(√n)）
     */
    public static long computePhi(long n) {
        long result = n;
        for (long p = 2; p * p <= n; p++) {
            if (n % p == 0) {
                // p是n的一个质因子
                while (n % p == 0) {
                    n /= p;
                }
                // 根据公式：φ(n) = n * Π(1 - 1/p)
                result = result / p * (p - 1);
            }
        }
        // 如果n还是大于1，说明n本身是质数
        if (n > 1) {
            result = result / n * (n - 1);
        }
        return result;
    }

    /**
     * 主函数：测试与演示
     */
    public static void main(String[] args) {
        int n = 100;
        EulerTotient et = new EulerTotient(n);

        System.out.println("前" + n + "个数的欧拉函数值：");
        for (int i = 1; i <= 20; i++) {
            System.out.printf("φ(%d) = %d%n", i, et.getPhi(i));
        }

        // 验证欧拉定理：a^φ(n) ≡ 1 (mod n)，其中gcd(a,n)=1
        int a = 3, mod = 7;
        int phiMod = et.getPhi(mod);
        long pow = 1;
        for (int i = 0; i < phiMod; i++) {
            pow = (pow * a) % mod;
        }
        System.out.printf("%n验证欧拉定理：%d^%d mod %d = %d%n", a, phiMod, mod, pow);

        // 大数测试
        long bigN = 123456789L;
        System.out.printf("φ(%d) = %d%n", bigN, computePhi(bigN));
    }
}

复杂度分析

线性筛法的核心思想是每个合数只被其最小质因子筛去一次，因此时间复杂度是线性的。在筛素数的过程中同步计算欧拉函数值，避免了二次遍历。

应用场景

• RSA加密：利用欧拉定理 a^φ(n) ≡ 1 (mod n) 进行加解密运算
• 模逆元计算：当 gcd(a,n)=1 时，a 的模 n 逆元为 a^(φ(n)-1) mod n
• 计数问题：求解与 n 互质且不超过 n 的正整数个数

总结

本文介绍了欧拉函数的定义、性质以及两种Java实现方式。线性筛法适合批量预处理，而质因数分解法适合单个查询。掌握欧拉函数不仅是数论学习的基础，也是理解现代密码学原理的关键一步。