数论基础（一）基本概念¶
章节概述¶
本章将介绍数论的基本概念，包括整除、约数、质数、合数、最大公约数和最小公倍数等。这些概念是学习数论的基础，在算法竞赛和密码学中都有广泛应用。
学习目标¶
- 理解整除和约数的概念
- 掌握质数和合数的判断方法
- 学会使用埃拉托斯特尼筛法和线性筛法求质数
- 掌握欧几里得算法求最大公约数
- 理解扩展欧几里得算法
- 学会求最小公倍数
（一）整除和约数¶
整除的定义¶
对于整数 a 和 b（b ≠ 0），如果存在整数 q，使得 a = b × q，则称 b 整除 a，记作 b | a。此时： - a 称为 b 的倍数 - b 称为 a 的约数（或因数）
基本性质¶
- 传递性：如果 a | b 且 b | c，则 a | c
- 线性性质：如果 a | b 且 a | c，则 a | (b ± c)
- 倍数性质：如果 a | b，则对于任意整数 k，有 a | (k × b)
代码实现：判断整除¶
def is_divisible(a, b):
"""
判断 b 是否整除 a
参数:
a: 被除数
b: 除数
返回:
bool: 如果 b 整除 a 返回 True，否则返回 False
示例:
>>> is_divisible(12, 3)
True
>>> is_divisible(12, 5)
False
"""
if b == 0:
return False
return a % b == 0
求约数¶
方法：遍历 1 到 √n，如果 i 整除 n，则 i 和 n/i 都是约数
def get_divisors(n):
"""
获取 n 的所有约数
参数:
n: 正整数
返回:
list: n 的所有约数，按升序排列
示例:
>>> get_divisors(12)
[1, 2, 3, 4, 6, 12]
>>> get_divisors(16)
[1, 2, 4, 8, 16]
"""
divisors = []
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
divisors.append(i)
if i != n // i: # 避免重复添加完全平方数的平方根
divisors.append(n // i)
return sorted(divisors)
时间复杂度：O(√n)
求约数个数¶
def count_divisors(n):
"""
计算 n 的约数个数
参数:
n: 正整数
返回:
int: 约数的个数
示例:
>>> count_divisors(12)
6
>>> count_divisors(16)
5
"""
count = 0
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
if i == n // i:
count += 1 # 完全平方数，平方根只计数一次
else:
count += 2
return count
求约数之和¶
def sum_divisors(n):
"""
计算 n 的所有约数之和
参数:
n: 正整数
返回:
int: 所有约数的和
示例:
>>> sum_divisors(12)
28 # 1 + 2 + 3 + 4 + 6 + 12 = 28
"""
total = 0
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
total += i
if i != n // i:
total += n // i
return total
（二）质数和合数¶
质数的定义¶
大于 1 的正整数，如果只有 1 和它本身两个约数，则称为质数（或素数）。否则称为合数。
质数的性质¶
- 2 是唯一的偶质数
- 大于 2 的质数都是奇数
- 算术基本定理：任何大于 1 的整数都可以唯一地表示为质数的乘积
- 质数有无穷多个
质数判断¶
方法一：试除法
import math
def is_prime(n):
"""
判断 n 是否为质数（试除法）
参数:
n: 正整数
返回:
bool: 如果 n 是质数返回 True，否则返回 False
时间复杂度: O(√n)
示例:
>>> is_prime(2)
True
>>> is_prime(17)
True
>>> is_prime(15)
False
"""
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
# 检查 6k±1 形式的数
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
优化说明： - 所有大于 3 的质数都可以表示为 6k±1 的形式 - 只需要检查到 √n
埃拉托斯特尼筛法（求质数）¶
原理：通过标记非质数来筛选出所有质数
def sieve_of_eratosthenes(n):
"""
埃拉托斯特尼筛法：求小于等于 n 的所有质数
参数:
n: 正整数
返回:
list: 小于等于 n 的所有质数
时间复杂度: O(n log log n)
空间复杂度: O(n)
示例:
>>> sieve_of_eratosthenes(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
"""
if n < 2:
return []
sieve = [True] * (n + 1)
sieve[0] = sieve[1] = False
# 从 2 开始，标记每个质数的倍数
for i in range(2, int(n**0.5) + 1):
if sieve[i]:
# 从 i² 开始标记，因为更小的倍数已经被更小的质数标记过
for j in range(i*i, n + 1, i):
sieve[j] = False
primes = [i for i, is_prime in enumerate(sieve) if is_prime]
return primes
优化版本：
def optimized_sieve(n):
"""
优化的埃拉托斯特尼筛法
优化点:
1. 只处理奇数（节省一半空间）
2. 从 i² 开始标记
"""
if n < 2:
return []
sieve = [True] * (n + 1)
sieve[0] = sieve[1] = False
# 处理 2
primes = [2] if n >= 2 else []
# 只处理奇数
for i in range(3, n + 1, 2):
if sieve[i]:
primes.append(i)
if i * i <= n:
for j in range(i*i, n + 1, 2*i):
sieve[j] = False
return primes
线性筛法（欧拉筛）¶
原理：保证每个合数只被其最小质因子标记一次
def linear_sieve(n):
"""
线性筛法（欧拉筛）：求小于等于 n 的所有质数
参数:
n: 正整数
返回:
list: 小于等于 n 的所有质数
时间复杂度: O(n)
空间复杂度: O(n)
示例:
>>> linear_sieve(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
"""
if n < 2:
return []
primes = []
is_composite = [False] * (n + 1)
for i in range(2, n + 1):
if not is_composite[i]:
primes.append(i)
# 用已找到的质数去标记合数
for p in primes:
if i * p > n:
break
is_composite[i * p] = True
if i % p == 0: # 关键：确保每个合数只被最小质因子标记一次
break
return primes
优势： - 时间复杂度为 O(n)，比埃拉托斯特尼筛法更快 - 适合处理大范围质数筛选
线段筛法（区间筛）¶
应用场景：求区间 [L, R] 内的质数，其中 R 很大但 R-L 较小
def segmented_sieve(L, R):
"""
线段筛法：求区间 [L, R] 内的所有质数
参数:
L: 区间下界
R: 区间上界
返回:
list: 区间内的所有质数
时间复杂度: O((R-L+1) log log R + √R log log √R)
示例:
>>> segmented_sieve(100, 150)
[101, 103, 107, 109, 113, 127, 131, 137, 139, 149]
"""
# 先筛出 √R 以内的质数
base_primes = sieve_of_eratosthenes(int(R**0.5))
# 初始化区间标记
segment = [True] * (R - L + 1)
for p in base_primes:
# 找到第一个 >= L 的 p 的倍数
start = max(p * p, ((L + p - 1) // p) * p)
for j in range(start, R + 1, p):
segment[j - L] = False
# 收集结果
primes = []
for i in range(R - L + 1):
if segment[i] and (L + i) >= 2: # 1 不是质数
primes.append(L + i)
return primes
（三）最大公约数和最小公倍数¶
最大公约数（GCD）¶
定义：能够同时整除两个或多个整数的最大正整数。
符号表示：gcd(a, b) 或 (a, b)
最小公倍数（LCM）¶
定义：能够被两个或多个整数同时整除的最小正整数。
符号表示：lcm(a, b) 或 [a, b]
GCD 与 LCM 的关系¶
对于正整数 a 和 b：
欧几里得算法（求 GCD）¶
原理：gcd(a, b) = gcd(b, a mod b)
def gcd(a, b):
"""
使用欧几里得算法求最大公约数
参数:
a, b: 整数
返回:
int: a 和 b 的最大公约数
时间复杂度: O(log min(a, b))
示例:
>>> gcd(12, 18)
6
>>> gcd(15, 25)
5
>>> gcd(0, 5)
5
"""
while b:
a, b = b, a % b
return abs(a)
递归版本：
扩展欧几里得算法¶
功能：不仅求出 gcd(a, b)，还求出整数 x, y 使得：
def extended_gcd(a, b):
"""
扩展欧几里得算法
参数:
a, b: 整数
返回:
tuple: (gcd, x, y)，使得 a*x + b*y = gcd(a, b)
时间复杂度: O(log min(a, b))
示例:
>>> gcd_val, x, y = extended_gcd(12, 18)
>>> print(f"GCD: {gcd_val}, x: {x}, y: {y}")
GCD: 6, x: -1, y: 1
>>> print(f"验证: 12*{x} + 18*{y} = {12*x + 18*y}")
验证: 12*-1 + 18*1 = 6
"""
if b == 0:
return abs(a), 1 if a > 0 else -1, 0
gcd_val, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return gcd_val, x, y
应用： - 求解线性同余方程 - 求模逆元 - 求解不定方程
求最小公倍数（LCM）¶
def lcm(a, b):
"""
求最小公倍数
参数:
a, b: 正整数
返回:
int: a 和 b 的最小公倍数
时间复杂度: O(log min(a, b))
示例:
>>> lcm(12, 18)
36
>>> lcm(15, 25)
75
"""
if a == 0 or b == 0:
return 0
return abs(a * b) // gcd(a, b)
求多个数的 GCD 和 LCM¶
def gcd_multiple(numbers):
"""
求多个数的最大公约数
参数:
numbers: 整数列表
返回:
int: 所有数的最大公约数
示例:
>>> gcd_multiple([12, 18, 24])
6
"""
if not numbers:
return 0
result = numbers[0]
for num in numbers[1:]:
result = gcd(result, num)
return result
def lcm_multiple(numbers):
"""
求多个数的最小公倍数
参数:
numbers: 正整数列表
返回:
int: 所有数的最小公倍数
示例:
>>> lcm_multiple([4, 6, 8])
24
"""
if not numbers:
return 0
result = numbers[0]
for num in numbers[1:]:
result = lcm(result, num)
return result
实战练习¶
练习1：完美数¶
问题：判断一个数是否为完美数（等于其所有真约数之和）
def is_perfect_number(n):
"""
判断 n 是否为完美数
完美数：等于其所有真约数（不包括自身）之和的数
例如：6 = 1 + 2 + 3
示例:
>>> is_perfect_number(6)
True
>>> is_perfect_number(28)
True
>>> is_perfect_number(12)
False
"""
if n <= 1:
return False
return sum_divisors(n) - n == n
练习2：亲和数¶
问题：判断两个数是否为亲和数（各自的真约数之和等于对方）
def are_amicable_numbers(a, b):
"""
判断两个数是否为亲和数
亲和数：a 的真约数之和等于 b，b 的真约数之和等于 a
例如：220 和 284 是亲和数
示例:
>>> are_amicable_numbers(220, 284)
True
>>> are_amicable_numbers(1184, 1210)
True
"""
if a == b:
return False
sum_a = sum_divisors(a) - a
sum_b = sum_divisors(b) - b
return sum_a == b and sum_b == a
练习3：第 n 个质数¶
问题：求第 n 个质数
def nth_prime(n):
"""
求第 n 个质数
参数:
n: 正整数
返回:
int: 第 n 个质数
示例:
>>> nth_prime(1)
2
>>> nth_prime(5)
11
>>> nth_prime(10)
29
"""
if n <= 0:
return None
count = 0
candidate = 2
while count < n:
if is_prime(candidate):
count += 1
if count == n:
return candidate
candidate += 1
return None
章节小结¶
本章介绍了数论的基本概念，包括：
- 整除和约数：理解整除的概念，掌握求约数的方法
- 质数和合数：学会判断质数，掌握埃拉托斯特尼筛法和线性筛法
- 最大公约数和最小公倍数：掌握欧几里得算法和扩展欧几里得算法
这些基础概念在后续章节中会频繁使用，请务必熟练掌握。
下一步¶
继续学习第二章：模运算，了解模运算的基本概念和模逆元。
练习答案提示： - 完美数：6, 28, 496, 8128, ... - 亲和数：(220, 284), (1184, 1210), (2620, 2924), ...