一、数学与数论：从素数到快速幂

数学与数论，听起来像是数学课的内容，对吧？但说实话，在算法面试里，这块内容出现的频率相当高。我个人习惯把这类问题归为「套路题」—— 一旦你掌握了几个核心模板，大部分题目都能迎刃而解。

今天我们就来聊聊三个最基础也最常用的数学工具：素数判断、最大公约数、快速幂。我会结合经典例题 Pow(x, n) 和质数计数，带你走一遍实战流程。

1. 素数判断：从暴力到优化

判断一个数是不是素数，这应该是每个程序员都写过的代码。但你真的写对了吗？

基础版：试除法

function isPrime(n) {
    if (n < 2) return false;
    for (let i = 2; i < n; i++) {
        if (n % i === 0) return false;
    }
    return true;
}

这个版本能跑，但效率太低了。n 很大的时候，循环次数接近 n 次。嗯，这里要注意：其实我们只需要检查到 √n 就够了。

优化版：检查到 √n

function isPrime(n) {
    if (n < 2) return false;
    if (n === 2) return true;
    if (n % 2 === 0) return false;
    for (let i = 3; i * i <= n; i += 2) {
        if (n % i === 0) return false;
    }
    return true;
}

为什么可以只检查到 √n？你想想看，如果 n 有一个大于 √n 的因子 a，那么必然存在一个小于 √n 的因子 b = n / a。所以检查到 √n 就够了。

我的经验： 在实际项目中，如果 n 的范围在 10^6 以内，这个优化版完全够用。我曾经在一个数据校验模块里用过这个写法，跑了几百万次都没问题。

2. 最大公约数：欧几里得算法

求两个数的最大公约数，最经典的方法就是欧几里得算法，也叫辗转相除法。说白了就是一句话：gcd(a, b) = gcd(b, a % b)。

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

这个算法的时间复杂度是 O(log min(a, b))，非常快。我记得有一次在写分数化简的模块时，就用到了这个算法，几行代码就搞定了。

避坑指南： 我曾经遇到过一个问题 —— 当 a 或 b 为 0 时，gcd 应该返回另一个数。很多初学者会忽略这个边界情况，导致程序崩溃。记得加上判断。

3. 快速幂：指数运算的利器

快速幂，顾名思义，就是快速计算 a^n 的方法。常规做法是循环 n 次，时间复杂度 O(n)。但快速幂可以做到 O(log n)。

核心思想是什么？把指数 n 写成二进制形式。比如计算 3^13，13 的二进制是 1101，那么 3^13 = 3^8 * 3^4 * 3^1。

function fastPow(base, exp) {
    let result = 1;
    while (exp > 0) {
        if (exp & 1) {  // 如果当前二进制位是1
            result *= base;
        }
        base *= base;
        exp >>= 1;  // 右移一位
    }
    return result;
}

这个写法很简洁，但要注意：如果指数很大，结果可能会溢出。实际工程中，我们通常会对结果取模。

4. 经典例题实战

例题一：Pow(x, n)

LeetCode 第 50 题，实现 pow(x, n)。这道题就是快速幂的典型应用，但要注意 n 可能是负数。

function myPow(x, n) {
    if (n === 0) return 1;
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    let result = 1;
    while (n > 0) {
        if (n & 1) result *= x;
        x *= x;
        n >>= 1;
    }
    return result;
}
注意： 当 n 为负数时，我们先把 x 取倒数，再把 n 变成正数。但这里有个坑 —— 如果 n 是 -2^31，取反后会溢出。所以更稳妥的做法是用 long 类型存储 n 的绝对值。

例题二：质数计数

LeetCode 第 204 题，统计小于 n 的质数个数。这道题如果用逐个判断的方法，时间复杂度是 O(n√n)，n 大了根本跑不动。

更好的方法是 埃拉托斯特尼筛法，简称埃氏筛。核心思想：从 2 开始，把每个质数的倍数都标记为合数。

function countPrimes(n) {
    if (n < 2) return 0;
    let isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;
    
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    let count = 0;
    for (let i = 2; i < n; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

为什么内层循环从 i*i 开始？因为 i 的较小倍数已经被更小的质数标记过了。这个优化能省掉不少重复操作。

我的建议： 埃氏筛的时间复杂度是 O(n log log n)，空间复杂度 O(n)。如果 n 在 10^7 以内，这个算法完全够用。但如果你需要处理更大的范围，可以考虑线性筛（欧拉筛），它能在 O(n) 时间内完成。

5. 知识体系总览

下面这张图总结了本章的核心知识点和它们之间的关系：

数学与数论基础 素数判断 试除法：检查到 √n 埃氏筛：标记倍数法 最大公约数 欧几里得算法（辗转相除法） 时间复杂度 O(log min(a,b)) 快速幂 二进制分解指数 时间复杂度 O(log n) 经典例题：Pow(x, n) 经典例题：质数计数 核心：掌握模板 + 注意边界 + 理解原理

6. 总结与避坑

好了，我们来快速回顾一下今天的内容：

  • 素数判断：试除法检查到 √n，批量判断用埃氏筛
  • 最大公约数：欧几里得算法，几行代码搞定
  • 快速幂：二进制分解，O(log n) 时间
  • 经典例题：Pow(x, n) 注意负数处理，质数计数用筛法
我曾经踩过的坑： 有一次在写质数计数时，我直接用了一个布尔数组，但忘了初始化。结果在 JavaScript 里，未初始化的数组元素是 undefined，被当作 true 处理了。嗯，这个小问题让我 debug 了半小时。所以记得显式初始化数组。

数学与数论这块，说白了就是几个固定套路。你只要把今天讲的三个模板练熟，再遇到相关题目，基本都能快速找到思路。下一章我们会继续深入，聊聊排列组合与概率统计，敬请期待。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →