常用小函数

有几个小函数在考试里会反复出现，写熟了能直接默出来，省下现推的时间：判断质数、求最大公约数、判断闰年、交换两数。这节先把判断质数吃透。

一个数 $n$（$n\ge 2$）是质数，就是除了 1 和它自己没有别的约数。最朴素是从 2 试到 $n-1$，但没必要试那么多：如果 $n$ 有一个大于 $\sqrt{n}$ 的约数，必然配着一个小于 $\sqrt{n}$ 的约数。所以只要试到 $\sqrt{n}$ 就够了。

bool isPrime(int n) {
    if (n < 2) return false;              // 0、1 不是质数
    for (int i = 2; (long long)i * i <= n; i++)
        if (n % i == 0) return false;     // 找到约数，不是质数
    return true;
}

这样复杂度从 $O(n)$ 降到 $O(\sqrt{n})$，$n$ 上百万也很快。

几个必记的坑：

• 1 和 0 都不是质数，2 是最小的质数（也是唯一的偶质数）。
• 循环条件用 i * i <= n 比 i <= sqrt(n) 更稳，避免浮点误差；i*i 可能溢出，大数据下转 long long。

下一节讲交换，再往后 gcd 用递归写，isLeap 上一节已给出，凑齐这四个就有了一套顺手的工具。