CC++ & Algorithm

Python数学知识辅助优化

较难3
语言版本：C++Python
概述：利用数学小技巧，比如只检查到平方根、用公式直接算，能大大减少程序的工作量。

用数学偷懒，让代码跑得更快 —— Python数学知识辅助优化

写程序时，我们常常会遇到一些“体力活”：反复循环、层层试探，就像考试时硬算一堆数。但数学告诉我们可以“走捷径”——利用规律直接得出结果，省时省力。下面咱们就看看怎么用数学小技巧让Python代码变聪明。

质数判断：只检查到平方根就够了

判断一个数是不是质数（素数），容易想到的做法是从2试除到n-1，看有没有能整除的。但数学上有个规律：如果一个数n有因子（除了1和它本身），那么至少有一个因子 ≤ √n。因为因子是成对出现的（比如12=3×4，3≤√12≈3.46，4≥√12），只要检查小的一半，另一半自然就知道了。所以只需要试除到√n，能省下很多计算。

生活例子：你想知道班级里有没有人和你身高一样，不需要跟全班每个人都比一次；只要先比身高比你矮的一半，如果都没有，那另一半里更不可能有和你一样高的（除非有双胞胎？但这个比喻帮助理解成对关系）。

代码中注意要处理n<2的情况，以及n=2、3等特殊值。另外，用int(math.sqrt(n)) + 1保证包含√n本身，因为range是左闭右开。

import math
import time

# 普通方法：从2试到n-1
def is_prime_slow(n):
    if n < 2:
        return False
    for i in range(2, n):          # i从2到n-1，逐个试除
        if n % i == 0:
            return False
    return True

# 优化方法：只试到sqrt(n)
def is_prime_fast(n):
    if n < 2:
        return False
    # 只检查到√n，注意要加1，因为range不包含上限
    limit = int(math.sqrt(n)) + 1
    for i in range(2, limit):
        if n % i == 0:
            return False
    return True

# 测试大一点的数
n = 9999991       # 一个较大的质数
start = time.time()
is_prime_slow(n)
print("普通方法用时:", time.time() - start)

start = time.time()
is_prime_fast(n)
print("优化方法用时:", time.time() - start)

你会发现优化方法快了几百倍甚至更多。对于100万的数，普通方法要检查近100万次，优化方法只检查1000次左右。

用数学公式直接求值：告别循环

很多求和的题目，比如“计算1加到100”，最直接的想法是循环累加。但等差数列求和公式 n*(n+1)//2 一步就能搞定，时间从O(n)变成O(1)。同样，平方和、立方和也有现成公式。

生活例子：你每天存零花钱，第一天存1元，第二天存2元，……第100天存100元，想知道总共存了多少。按公式算秒出结果，不用一天一天加。

# 不用公式：循环累加
total = 0
for i in range(1, 101):  # 从1到100
    total += i
print("循环求和:", total)

# 用公式：直接计算 n*(n+1)//2
n = 100
total = n * (n + 1) // 2   # 记得用整数除法，避免浮点数
print("公式求和:", total)

平方和公式：1² + 2² + … + n² = n(n+1)(2n+1) / 6
例如，求1到10的平方和：

n = 10
square_sum = n * (n + 1) * (2 * n + 1) // 6
print("1到10的平方和:", square_sum)
# 验证循环
total = 0
for i in range(1, n+1):
    total += i * i
print("循环验证:", total)

立方和公式：1³ + 2³ + … + n³ = [n(n+1)/2]²
注意先算括号内的除法，最好用整数除法或分数保持精确。

n = 10
cube_sum = (n * (n + 1) // 2) ** 2
print("1到10的立方和:", cube_sum)

公式不仅快，而且对于大数（比如n=10^6）循环会超时，公式瞬间完成。

其他经典数学小技巧

判断完全平方数

检查一个数是不是完全平方数，可用 int(math.sqrt(n)) ** 2 == n。但浮点数计算可能有精度误差（比如对非常大的数），更稳妥的方式是使用 math.isqrt（Python 3.8+），它返回整数平方根。

import math

def is_perfect_square(n):
    if n < 0:
        return False
    root = math.isqrt(n)   # 返回整数平方根
    return root * root == n

print(is_perfect_square(25))  # True
print(is_perfect_square(26))  # False

最大公约数（GCD）：欧几里得算法

求两个数的最大公约数，用辗转相除法（欧几里得算法）比循环试除快得多。

def gcd_euclid(a, b):
    while b != 0:
        a, b = b, a % b   # 连续取余
    return a

print(gcd_euclid(48, 18))  # 输出6

对比循环试除（从min(a,b)往下试）就慢很多。

判断奇偶

用 n % 2 == 0 判断偶数，比用 n & 1 == 0 位运算也很常见，但位运算更快一点点。

交换变量

a, b = b, a 利用元组解包，不用临时变量，简洁又高效。

新手容易犯的错误

  1. 质数判断忘记特殊值

    • 忘了处理n=1（不是质数）、n=2（最小的质数，循环不会执行，返回True正确）。
    • 忘了处理n=3（√3≈1.73，循环从2开始，但range(2, 1)不会执行，也正确）。
    • 但是，如果写成int(math.sqrt(n))而不是+1，对完全平方数可能漏判：比如n=4，√4=2，int(2)=2，range(2,2)为空，不会检查2是否能整除4，导致错误地返回True。

    正确做法：limit = int(math.sqrt(n)) + 1，或者用math.isqrt(n) + 1。

  2. 公式使用浮点除法
    比如 n*(n+1)/2 返回浮点数，当n较大时浮点数可能丢失精度。应使用整数除法 //。

  3. 时间测试只做一次
    程序中调用一次函数可能受系统影响，应该多测几次取平均，或使用timeit模块。

  4. 大数平方根精度问题
    math.sqrt返回浮点数，对于超大整数（比如大于2^53）可能不精确。建议使用math.isqrt（Python 3.8+）或整数二分法。

完整可运行的示例：质数判断 + 求和优化对比

下面给一个整合例子，包含两种优化，并比较时间。

import math
import time

# ---------- 质数判断 ----------
def is_prime_normal(n):      # 普通方法，从2到n-1
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def is_prime_fast(n):        # 优化方法，只到平方根
    if n < 2:
        return False
    limit = int(math.sqrt(n)) + 1
    for i in range(2, limit):
        if n % i == 0:
            return False
    return True

# ---------- 求和公式 ----------
def sum_loop(n):             # 循环求和
    total = 0
    for i in range(1, n+1):
        total += i
    return total

def sum_formula(n):          # 公式求和
    return n * (n + 1) // 2

# ---------- 测试 ----------
n = 1000000   # 百万级别
start = time.time()
is_prime_normal(n)          # 普通方法很慢，但不打印结果，只测时间
print("普通质数判断用时:", time.time() - start)

start = time.time()
is_prime_fast(n)
print("优化质数判断用时:", time.time() - start)

# 求和测试
start = time.time()
s1 = sum_loop(10000000)     # 千万级别
print("循环求和用时:", time.time() - start)

start = time.time()
s2 = sum_formula(10000000)
print("公式求和用时:", time.time() - start)
print("两者结果是否相等:", s1 == s2)

运行结果会看到优化后的方法快几个数量级。

相关指引

数学优化只是算法优化的一部分。如果想继续深入，可以学习：

  • 动态规划：用表格记录中间结果，避免重复计算（比如斐波那契数列）。
  • 二分查找：在有序数据中快速定位，代替线性搜索。
  • 哈希表：用空间换时间，快速判断元素是否存在。
  • 位运算技巧：比如判断2的幂、交换、奇偶等。
  • Python内置库：math、itertools、functools.lru_cache 等也能帮忙优化。

记住：写代码前先想想有没有数学规律，往往能让你一招制胜！

例题精讲

1单选题

在判断一个整数n(n>1)是否为素数时，以下哪种做法利用了数学知识辅助优化，可以显著减少循环次数？

A从2循环到n，检查是否有因子
B从2循环到n//2，检查是否有因子
C从2循环到int(n**0.5)+1，检查是否有因子
D从2循环到n-1，检查是否有因子
2判断题

计算1+2+3+...+n的值时，使用公式n*(n+1)//2比使用循环累加更高效，这体现了数学知识辅助优化。

3填空题
以下代码使用埃拉托色尼筛法求小于等于n的所有素数。请填空优化内层循环的起始位置，避免重复标记。

def sieve(n):
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(___, n+1, i):
                is_prime[j] = False
    return [i for i in range(2, n+1) if is_prime[i]]
4单选题

计算两个正整数a和b的最大公约数时，以下哪种算法利用了数学优化（辗转相除法）？

A枚举从1到min(a,b)的所有整数，找到最大公因子
B循环计算a%b，然后交换a和b，直到b=0
C使用math.gcd(a,b)直接调用库函数
D分解a和b的质因数，取公共部分
5填空题
判断一个正整数n是否为完全数（所有真因子之和等于n，例如6=1+2+3）。下面代码利用数学优化只检查到平方根。请填空。

def is_perfect(n):
    if n < 2:
        return False
    sum_div = 1
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            sum_div += i
            if i != n // i:
                sum_div += ___
    return sum_div == n