← 知识手册目录算法方法 · GESP 5 / 8 级相关跳到完整速查 ↓

PYTHON KNOWLEDGE · 13

质数、约数、最大公因数与筛法

建立整数整除体系，掌握试除、欧几里得算法、唯一分解和筛法的条件与复杂度。

GESP 5 级GESP 8 级

01 · FORMAL DEFINITION

正式定义

若整数 a 能被非零整数 b 整除，则 b 是 a 的约数。大于 1 且只有 1 和自身两个正约数的整数是质数；每个大于 1 的整数都能唯一分解为质数幂的乘积（忽略次序）。

02 · MUST KNOW

学完这一章，必须说清楚的规则

  1. 01

    0 和 1 都不是质数；判定 n 是否为质数只需试除到 floor(sqrt(n))。

  2. 02

    gcd(a,b)=gcd(b,a mod b) 构成欧几里得算法；lcm(a,b)=abs(a//gcd(a,b)*b) 并要处理 0。

  3. 03

    约数成对出现，可枚举到平方根；完全平方数的平方根只计一次。

  4. 04

    埃氏筛从 p² 开始标记质数 p 的倍数，总体 O(n log log n)；线性筛保证每个合数被最小质因子筛一次。

  5. 05

    分解质因数后，约数个数与约数和可以由各质因数指数公式计算。

  6. 06

    模运算支持加减乘分配；模除法不能直接用整数除法，需满足可逆条件并求逆元。

03 · RUNNABLE EXAMPLE

可运行示例与因果解释

PYTHON
from math import gcd, isqrt

def is_prime(n):
    if n < 2:
        return False
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            return False
    return True

print(gcd(84, 30), is_prime(97))

COMMON PITFALLS

常见误区

  • 把 1 判成质数
  • 试除上界漏掉平方根
  • 完全平方数的约数重复统计
  • 取模后直接做普通除法

SCOPE & BOUNDARIES

适用边界

  • 大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
  • 题目若涉及负数约数、0 的约数或模数非质数，必须先明确数学定义。