编程内功心法：素数判定、高精度计算与二分查找等基础算法精讲

1. 从零到一为什么这些基础算法是编程的“内功心法”最近在带新人或者看一些开源项目的代码时我总有一个感觉很多朋友在解决复杂问题时思路很活跃框架用得也很溜但一旦遇到需要自己动手处理一些“数学”或者“边界”问题时就容易卡壳。比如给你一个很大的数让你判断它是不是素数或者给你两个超长的字符串让你模拟它们的加减法。这些问题往往不依赖任何花哨的库考验的就是你对基础算法的理解和实现能力。标题里提到的这几个概念——素数、质因数、最大公约数、高精度加减、二分函数、前缀和——它们就像武侠小说里的“内功心法”。你可能不会天天用降龙十八掌某个复杂的深度学习框架但深厚的内功这些基础算法能让你学任何新招式都事半功倍并且在面对一些看似简单、实则暗藏玄机的问题时能够从容不迫地拆解。我见过太多项目性能瓶颈或者诡异的Bug追根溯源最后都落在了这些基础数据处理的效率或正确性上。今天我就结合自己这些年踩过的坑和积累的经验把这些“内功心法”系统地梳理一遍不仅告诉你它们是什么更重点讲清楚在不同场景下该怎么选、怎么用、怎么避坑。2. 数论基石素数判定、质因数分解与最大公约数的实战精讲数论相关的算法是很多高级算法如RSA加密的基础也是竞赛和面试中的常客。理解它们的关键不在于死记模板而在于明白其背后的数学原理和效率权衡。2.1 素数判定从暴力枚举到高效筛法判断一个数n是否为素数最直接的想法是看它能否被2到n-1之间的数整除。但稍加优化我们只需要检查到√n即可因为如果n有一个大于√n的因子那么它必然对应一个小于√n的因子。def is_prime_naive(n: int) - bool: if n 2: return False if n 2: return True if n % 2 0: return False # 只需检查奇数因子到sqrt(n)为止 i 3 while i * i n: if n % i 0: return False i 2 return True对于单个数的判定这个方法在n不大时比如10^12以内完全够用。但如果你需要频繁判断一个大范围内比如1到10^7的所有数是否为素数逐个判断的O(n√n)复杂度就不可接受了。这时就需要埃拉托斯特尼筛法埃筛。埃筛的思想非常巧妙假设所有数初始都是素数然后从2开始将其倍数全部标记为非素数。那么下一个未被标记的数就是下一个素数继续标记其倍数。def sieve_of_eratosthenes(n: int): 返回一个布尔列表 is_primeis_prime[i] 表示 i 是否为素数 (0 i n)。 同时返回一个素数列表 primes。 is_prime [True] * (n 1) is_prime[0] is_prime[1] False primes [] for i in range(2, n 1): if is_prime[i]: primes.append(i) # 从 i*i 开始标记因为 i*(i-1) 等已经被更小的素数标记过了 if i * i n: # 防止 i*i 溢出 for j in range(i * i, n 1, i): is_prime[j] False return is_prime, primes注意标记倍数时从i*i开始是关键优化。例如对于素数552、53、5*4其实已经在处理素数2和3时被标记过了。这个细节能省去大量重复操作。埃筛的时间复杂度是O(n log log n)空间O(n)。对于标题热词中提到的“n10000000”这个量级埃筛可以在毫秒级完成。但埃筛有一个小问题一个合数可能被多个素数标记比如6会被2和3都标记一次。欧拉筛线性筛解决了这个问题确保每个合数只被其最小质因子标记一次时间复杂度严格O(n)。它的实现需要多维护一个质数列表。def linear_sieve(n: int): is_prime [True] * (n 1) primes [] for i in range(2, n 1): if is_prime[i]: primes.append(i) for p in primes: if p * i n: break is_prime[p * i] False # 关键如果 i 能被 p 整除那么 i * p (p p) 的最小质因子就不是 p 了而是 p。 # 所以此时跳出避免重复标记。 if i % p 0: break return is_prime, primes选择建议单次或少量查询用优化后的试除法is_prime_naive。需要预处理一个区间内所有数的素数情况用埃筛代码简单效率足够。对时间复杂度极其敏感或者需要同步获取每个数的最小质因子用线性筛。2.2 质因数分解将数拆解为“积木”质因数分解是将一个合数表示为一系列素数乘积的过程。它是理解数论问题的另一把钥匙比如求约数个数、欧拉函数等。最直接的方法是用试除法从小到大尝试素数去整除。def prime_factorization(n: int): 返回一个列表每个元素是 (质因子, 指数) 的元组。 factors [] # 先处理因子2 cnt 0 while n % 2 0: n // 2 cnt 1 if cnt 0: factors.append((2, cnt)) # 处理奇数因子 p 3 while p * p n: if n % p 0: cnt 0 while n % p 0: n // p cnt 1 factors.append((p, cnt)) p 2 # 如果最后剩下的n大于1它本身就是一个质数 if n 1: factors.append((n, 1)) return factors # 示例分解 360 # 输出[(2, 3), (3, 2), (5, 1)] 表示 360 2^3 * 3^2 * 5效率关键在试除时我们只需要循环到√n。因为n最多只可能有一个大于√n的质因子如果有两个乘积就超过n了这个因子就是循环结束后剩下的那个n。实战技巧如果需要频繁对多个数进行质因数分解可以先用线性筛预处理出一定范围内每个数的最小质因子。这样分解任何一个数时我们可以不断地除以它的最小质因子将复杂度从O(√n)降至O(log n)。2.3 最大公约数(GCD)与最小公倍数(LCM)高效的欧几里得算法求两个数的最大公约数最著名也最高效的方法是辗转相除法欧几里得算法。它的核心原理是gcd(a, b) gcd(b, a % b)。当余数为0时除数就是最大公约数。def gcd_euclidean(a: int, b: int) - int: 递归实现 if b 0: return a return gcd_euclidean(b, a % b) def gcd_iterative(a: int, b: int) - int: 迭代实现更节省栈空间推荐 while b ! 0: a, b b, a % b return aPython的标准库math中已经提供了高度优化的gcd函数直接import math; math.gcd(a, b)即可。对于求多个数的最大公约数可以利用functools.reduce。import math from functools import reduce gcd_two math.gcd(12, 18) # 6 list_nums [12, 18, 24] gcd_multi reduce(math.gcd, list_nums) # 6为什么是reducereduce函数会将前两个元素的计算结果与下一个元素继续计算。reduce(gcd, [a, b, c])等价于gcd(gcd(a, b), c)这正是我们想要的。有了最大公约数求最小公倍数就很简单了lcm(a, b) a * b / gcd(a, b)。但要注意整数溢出问题在Python中整数无限大没问题但在C/Java中更安全的写法是a / gcd(a, b) * b先除后乘。3. 突破语言限制手把手实现高精度整数加减法编程语言的基本数据类型如int,long long都有其表示范围。当我们需要处理远超此范围的整数时例如1000位的数字就必须自己模拟竖式计算这就是高精度计算。这里我们先从最基础的加减法开始。3.1 核心思想用数组模拟大数我们无法用一个变量存储整个大数但可以用一个数组或列表来存储它的每一位。为了方便计算尤其是进位我们通常采用倒序存储即数组的第0位arr[0]存储个位第1位存储十位以此类推。例如数字123456789我们存储为列表[9, 8, 7, 6, 5, 4, 3, 2, 1]。3.2 高精度加法实现加法的过程就是模拟竖式从低位到高位逐位相加处理进位。def high_precision_add(num1_str: str, num2_str: str) - str: 输入两个非负整数字符串返回它们的和字符串。 核心倒序存储逐位相加处理进位。 # 1. 将字符串转换为倒序的整数列表 A [int(digit) for digit in reversed(num1_str)] B [int(digit) for digit in reversed(num2_str)] # 2. 确保A是较长的那个方便后续处理 if len(A) len(B): A, B B, A # 3. 逐位相加 carry 0 # 进位 C [] # 存储结果 for i in range(len(A)): # 获取B的当前位如果B已经用完则为0 digit_b B[i] if i len(B) else 0 total A[i] digit_b carry C.append(total % 10) # 当前位结果 carry total // 10 # 新的进位 # 4. 处理最后的进位 if carry: C.append(carry) # 5. 将结果列表反转并拼接成字符串 return .join(str(digit) for digit in reversed(C)) # 测试 print(high_precision_add(99999999999999999999, 1)) # 输出100000000000000000000关键细节与避坑输入处理一定要先处理字符串直接转int可能已经溢出。确保输入是合法的数字字符串。长度处理让A始终是较长的数可以简化循环内的边界判断。进位处理循环结束后必须检查最后的carry是否为1这是新手最容易忘记的一步。前导零我们的实现不会产生前导零但如果输入有前导零如00123最好在函数开始处去除或者保证输入规范。3.3 高精度减法实现减法比加法复杂一些因为涉及借位和判断正负。def high_precision_sub(num1_str: str, num2_str: str) - str: 假设 num1 num2返回它们的差字符串。 如果可能小于需要在外层判断。 # 比较大小确保 A B if len(num1_str) len(num2_str) or (len(num1_str) len(num2_str) and num1_str num2_str): # 此时结果为负可以抛出异常或返回带符号的结果这里先简单处理 return - high_precision_sub(num2_str, num1_str) A [int(digit) for digit in reversed(num1_str)] B [int(digit) for digit in reversed(num2_str)] C [] borrow 0 # 借位 for i in range(len(A)): digit_a A[i] - borrow # 先减去上一位的借位 digit_b B[i] if i len(B) else 0 if digit_a digit_b: # 需要向高位借1当10 digit_a 10 borrow 1 else: borrow 0 C.append(digit_a - digit_b) # 去除结果中的前导零倒序存储时前导零在列表尾部 while len(C) 1 and C[-1] 0: C.pop() return .join(str(digit) for digit in reversed(C)) # 测试 print(high_precision_sub(1000, 999)) # 输出1 print(high_precision_sub(123, 456)) # 输出-333减法核心难点大小判断必须确保被减数不小于减数否则结果会是负数。我们需要一个独立的函数来比较两个高精度数的大小。借位处理借位的逻辑是“当前位不够减时向高位借1当10并将借位标志置为1在计算下一位时先减去这个借位”。去除前导零比如100-9901我们需要去掉结果的0变成1。在倒序列表中前导零位于末尾。个人心得实现高精度运算时画一个竖式图在旁边对照每一步的代码是调试和理解最快的方法。另外务必为加减乘除分别编写独立的比较函数cmp这在处理复杂表达式时至关重要。4. 二分查找不止于“查找”的万能优化思想二分查找通常被理解为在一个有序数组中快速定位目标值。这没错但它的威力远不止于此。更本质地看二分法是一种在单调有序问题上将线性搜索优化为对数级搜索的通用策略。4.1 标准二分查找模板与细节先看最经典的场景在一个升序无重复数组nums中查找目标值target找到返回索引否则返回-1。def binary_search_exact(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 # 防止(leftright)溢出 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1这个模板的关键是循环条件left right和区间更新mid ± 1。它确保了搜索区间不断缩小直到找到目标或区间无效。4.2 二分查找的变体寻找边界实际问题中数组可能包含重复元素。我们常常需要找到target的第一个或最后一个位置。这是二分查找最容易出错的地方。寻找左边界第一个 target 的位置def binary_search_left_bound(nums, target): left, right 0, len(nums) # 注意 right 初始为 len(nums) while left right: # 循环条件变了 mid left (right - left) // 2 if nums[mid] target: right mid # 收紧右边界即使相等也继续向左找 else: left mid 1 # 循环结束时 left right # 检查 left 是否越界以及找到的是否真的是 target if left len(nums) and nums[left] target: return left return -1这个写法搜索的是第一个大于等于target的位置。当nums[mid] target时我们不立即返回而是让right mid继续向左半部分搜索从而找到最左边的那个。寻找右边界最后一个 target 的位置def binary_search_right_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 # 收紧左边界即使相等也继续向右找 else: right mid # 循环结束时 left right # left 是第一个大于 target 的位置所以 left - 1 可能是 target if left - 1 0 and nums[left - 1] target: return left - 1 return -1记忆技巧寻找左边界时mid满足条件target就移动right寻找右边界时mid满足条件target就移动left。循环结束后根据需求对left或left-1进行校验。4.3 二分答案解决“最大值最小化”问题这是二分查找最强大的应用之一。当问题可以转化为“求满足某个条件C(x)的最小/最大x”并且条件C(x)关于x具有单调性即如果x满足那么所有大于/小于x的值也满足或不满足时就可以对答案x进行二分搜索。经典例题给定一个正整数数组和一个整数k你需要将这个数组分成k个连续的非空子数组。最小化这k个子数组各自和的最大值。我们无法直接求出这个“最大和的最小值”但我们可以二分搜索这个值。对于一个猜测的答案mid即假设每个子数组的和不超过mid我们可以贪心地去划分数组从左到右累加一旦当前子数组和超过mid就新开一个子数组。最后统计需要的子数组数量。如果需要的数量 k说明mid这个限制是可行的且可能偏大我们可以尝试更小的mid所以令right mid。如果需要的数量 k说明mid太小了限制太严格需要令left mid 1。def split_array(nums, k): def can_split(max_sum): 判断在最大子数组和不超过max_sum的情况下能否分成最多k份 count 1 current_sum 0 for num in nums: if current_sum num max_sum: count 1 current_sum num if count k: return False else: current_sum num return True left, right max(nums), sum(nums) # 答案的下界和上界 while left right: mid left (right - left) // 2 if can_split(mid): right mid else: left mid 1 return left二分答案的步骤确定答案的搜索范围[left, right]。设计一个单调的判定函数check(mid)判断mid作为答案是否可行。根据check(mid)的结果决定搜索区间如何收缩。通常如果mid可行就尝试更小的值right mid如果不可行就尝试更大的值left mid 1。循环结束时left或right就是最优解。5. 前缀和与差分区间操作的“降维打击”利器当题目频繁要求计算数组某个区间[l, r]的和或者需要对某个区间进行统一加减操作时暴力循环的O(n)复杂度会成为瓶颈。前缀和与差分技术能将这类区间查询或更新操作优化到O(1)。5.1 前缀和快速计算区间和前缀和的核心是预处理一个数组pre其中pre[i]表示原数组arr前i个元素的和通常pre[0]0。即pre[i] arr[0] arr[1] ... arr[i-1]那么区间[l, r]的和下标从0开始包含两端就可以通过sum(l, r) pre[r1] - pre[l]在O(1)时间内得到。class PrefixSum: def __init__(self, nums): n len(nums) self.pre [0] * (n 1) for i in range(n): self.pre[i 1] self.pre[i] nums[i] def query_range_sum(self, l: int, r: int) - int: 查询闭区间 [l, r] 的和下标从0开始 return self.pre[r 1] - self.pre[l] # 使用示例 nums [1, 2, 3, 4, 5] ps PrefixSum(nums) print(ps.query_range_sum(1, 3)) # 输出9 (234)为什么pre长度是n1且pre[0]0这是为了统一处理从0开始的区间。sum(0, r)本应等于pre[r1] - pre[0]如果pre[0]0公式依然成立。这个设计让代码更简洁不易出错。5.2 差分快速进行区间更新差分是前缀和的逆运算。给定一个数组arr其差分数组diff定义为diff[i] arr[i] - arr[i-1]对于i0且diff[0] arr[0]。差分数组的妙用在于如果想对原数组的区间[l, r]统一加上一个值val只需要在差分数组上修改两个点diff[l] valdiff[r1] - val如果r1未越界然后对差分数组求前缀和就能得到更新后的原数组。class Difference: def __init__(self, nums): n len(nums) self.diff [0] * n self.diff[0] nums[0] for i in range(1, n): self.diff[i] nums[i] - nums[i-1] def increment_range(self, l: int, r: int, val: int): 给闭区间 [l, r] 的所有元素增加 val self.diff[l] val if r 1 len(self.diff): self.diff[r 1] - val def get_result(self): 根据差分数组还原原数组 res [0] * len(self.diff) res[0] self.diff[0] for i in range(1, len(self.diff)): res[i] res[i-1] self.diff[i] return res # 使用示例 nums [1, 2, 3, 4, 5] df Difference(nums) df.increment_range(1, 3, 10) # 给下标1,2,3的元素加10 result df.get_result() print(result) # 输出[1, 12, 13, 14, 5]差分的思想将对一个区间的操作转化为对区间两端点的操作。当有大量区间更新操作时先记录在差分数组上最后只做一次前缀和就能得到最终结果将每次更新O(n)的复杂度降为O(1)记录 O(n)重建。5.3 二维前缀和与差分问题扩展到二维矩阵上原理是相通的。二维前缀和pre[i][j]表示从(0,0)到(i-1, j-1)的子矩阵和。 预处理pre[i][j] matrix[i-1][j-1] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1]查询子矩阵(x1,y1)到(x2,y2)的和sum pre[x21][y21] - pre[x1][y21] - pre[x21][y1] pre[x1][y1]二维差分对子矩阵(x1,y1)到(x2,y2)统一加val只需修改差分矩阵的四个角diff[x1][y1] valdiff[x21][y1] - valdiff[x1][y21] - valdiff[x21][y21] val最后对diff求二维前缀和即得更新后的矩阵。实战经验前缀和与差分的问题在纸上画出矩阵标出坐标推导一遍公式比死记硬背有效得多。尤其要注意下标是0-based还是1-based统一一种风格我习惯在预处理时使用n1的大小让查询公式更统一。遇到复杂问题时先考虑能否转化成一维问题或者用多个一维前缀和/差分组合解决。6. 融会贯通综合案例与性能抉择掌握了这些基础组件后真正的考验在于如何将它们组合起来解决复杂问题并做出正确的性能取舍。6.1 案例统计区间内素数个数结合筛法与前缀和题目多次查询每次给出[L, R]求该区间内素数的个数。L, R最大可能到10^7查询次数Q可达10^5。暴力法不可行对每次查询用试除法判断区间内每个数复杂度O(Q * (R-L) * √R)无法承受。高效解法预处理使用埃筛或线性筛预处理出1到MAX_R比如10^7范围内每个数是否为素数。构建前缀和数组创建一个数组prime_count其中prime_count[i]表示从1到i的素数个数。这可以在筛法完成后一次遍历得到prime_count[i] prime_count[i-1] (1 if is_prime[i] else 0)。回答查询对于每次查询[L, R]答案就是prime_count[R] - prime_count[L-1]。每次查询时间复杂度O(1)。def solve_range_prime_count(max_n, queries): # 1. 筛法求素数 is_prime, _ sieve_of_eratosthenes(max_n) # 使用埃筛 # 2. 构建素数个数的前缀和 prime_cnt [0] * (max_n 1) for i in range(2, max_n 1): prime_cnt[i] prime_cnt[i-1] (1 if is_prime[i] else 0) # 3. 回答查询 results [] for L, R in queries: # 注意边界L可能为1 ans prime_cnt[R] - prime_cnt[L-1] if L 1 else prime_cnt[R] results.append(ans) return results这个案例完美结合了筛法预处理和前缀和快速查询的思想。6.2 性能权衡何时自己实现何时调用库这是一个很实际的问题。以最大公约数为例Python的math.gcd是用C实现的效率极高。99%的情况你都应该直接用它。那为什么我们还要学习欧几里得算法的原理和实现理解原理应对变体你可能需要求解ax by gcd(a, b)的整数解扩展欧几里得算法这是RSA等加密算法的基础库函数没有直接提供。处理特殊数据库函数通常处理的是标准整数。如果你自己实现了高精度整数类就需要为其重载GCD运算。面试与竞赛这是考察你基本功的经典题目。性能极致优化在某些底层或受限环境中你可能需要针对特定数据范围如全是偶数进行位运算优化更相减损术的二进制版本。通用建议高精度运算除非有极其可靠且高效的第三方库如Python的decimal模块用于高精度浮点int本身支持任意大整数否则在竞赛或对性能有要求的场景中自己实现是常态。二分查找Python的bisect模块提供了高效的二分查找函数对于标准查找需求应优先使用。但“二分答案”这种模式化的应用通常需要自己编写check函数。前缀和/差分这类思想性的算法库函数无法直接提供必须自己编码实现。6.3 调试技巧与常见“坑点”二分查找的死循环与边界while left right与while left right的选择以及mid的取整(leftright)//2是向下取整是导致死循环或漏查的元凶。记住一个原则明确搜索区间。[left, right]和[left, right)对应不同的初始化和更新方式。最稳妥的方法是固定使用一种写法如左闭右开[left, right)并透彻理解。高精度运算的输入与输出确保输入是字符串输出也是字符串。特别注意减法结果可能为0去除前导零时要保留至少一位。筛法的内存与速度埃筛is_prime列表可以用bytearray或bitarray来节省内存。线性筛虽然理论复杂度低但常数较大在n10^7量级以下埃筛的实际运行速度往往更快。前缀和的下标偏移这是最大的易错点。坚持使用pre[i]表示前i个元素的和pre[0]0那么区间[l, r]的和就是pre[r1] - pre[l]。在纸上画个例子就能清晰理解。把这些基础算法吃透形成肌肉记忆你在面对更复杂的系统设计、算法优化时会发现很多问题都能被拆解成这些基础模块的组合。它们是你编程工具箱里最常用也最可靠的那几把扳手。