前言

在计算机科学中，算法是解决问题的核心工具。而数学问题往往能为我们提供绝佳的算法练习场景——它们逻辑清晰、边界明确、结果可验证。本文将围绕“哥德巴赫猜想”、“埃拉托色尼筛法”等经典数学主题，设计8道兼具趣味性与挑战性的算法题，并逐一进行思想分析、代码实现与演练演示。

无论你是初学者还是进阶开发者，这些题目都能帮助你深入理解算法思维、提升编码能力，并感受数学与编程交融之美。

一、哥德巴赫猜想的并行验证（多线程/多进程）

题目：

编写一个程序，使用多线程或多进程方式，验证从4到N的所有偶数是否都可以表示为两个质数之和（哥德巴赫猜想）。要求输出每个偶数的分解形式（如 6 = 3 + 3），并统计验证成功的数量。

算法思想基础：

• 哥德巴赫猜想：任一大于2的偶数都可写成两个质数之和。
• 并行化处理：将区间 [4, N] 分割成若干子区间，由多个线程/进程分别处理，提高效率。
• 质数判断：可用试除法或预生成质数表加速。

实现思路：

1. 编写 is_prime(n) 函数判断质数。
2. 编写 goldbach_verify(even_num) 函数寻找两个质数之和等于该偶数。
3. 使用 concurrent.futures.ThreadPoolExecutor 或 ProcessPoolExecutor 并行执行。
4. 收集结果并汇总。

算法演练：

输入 N=20，输出：

4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17
共验证9个偶数，全部成功！

代码实现：

# filename: goldbach_parallel.py
import concurrent.futures
from math import sqrt

def is_prime(n):
    """判断是否为质数"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

def goldbach_verify(even_num):
    """验证偶数能否表示为两质数之和"""
    for i in range(2, even_num // 2 + 1):
        if is_prime(i) and is_prime(even_num - i):
            return f"{even_num} = {i} + {even_num - i}"
    return None

def main():
    N = 20
    results = []
    
    # 使用线程池并行处理
    with concurrent.futures.ThreadPoolExecutor() as executor:
        futures = [executor.submit(goldbach_verify, num) for num in range(4, N+1, 2)]
        for future in concurrent.futures.as_completed(futures):
            result = future.result()
            if result:
                print(result)
                results.append(result)
    
    print(f"共验证{len(results)}个偶数，全部成功！")

if __name__ == "__main__":
    main()

二、埃拉托色尼筛法：高效寻找质数

题目：

实现埃拉托色尼筛法，找出小于等于N的所有质数，并返回质数列表及个数。

算法思想基础：

• 埃氏筛法原理：从2开始，标记所有倍数为合数，剩余未被标记即为质数。
• 时间复杂度 O(N log log N)，空间复杂度 O(N)。

实现思路：

1. 创建布尔数组 is_prime[0..N]，初始全为True。
2. 从2开始遍历，若当前数为质数，则将其所有倍数标记为False。
3. 最后收集所有仍为True的索引。

算法演练：

输入 N=30，输出：

质数列表: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
质数个数: 10

代码实现：

# filename: sieve_of_eratosthenes.py
def sieve_of_eratosthenes(n):
    """埃拉托色尼筛法求质数"""
    if n < 2:
        return []
    
    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]:
            # 标记i的所有倍数为非质数
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    
    primes = [i for i, prime in enumerate(is_prime) if prime]
    return primes

def main():
    N = 30
    primes = sieve_of_eratosthenes(N)
    print(f"质数列表: {primes}")
    print(f"质数个数: {len(primes)}")

if __name__ == "__main__":
    main()

三、回文质数：对称之美

题目：

找出小于等于N的所有“回文质数”（既是质数又是回文数的数字）。

算法思想基础：

• 回文数：正读反读相同，如121、131。
• 结合质数判断与回文判断。

实现思路：

1. 遍历1到N。
2. 对每个数先判断是否为回文，再判断是否为质数。
3. 优化：可先生成回文数再判断质数，减少计算量。

算法演练：

输入 N=200，输出：

回文质数: [2, 3, 5, 7, 11, 101, 131, 151, 181, 191]

代码实现：

# filename: palindrome_primes.py
def is_palindrome(n):
    """判断是否为回文数"""
    s = str(n)
    return s == s[::-1]

def is_prime(n):
    """判断是否为质数"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

def find_palindrome_primes(n):
    """查找小于等于n的回文质数"""
    result = []
    for i in range(2, n+1):
        if is_palindrome(i) and is_prime(i):
            result.append(i)
    return result

def main():
    N = 200
    pal_primes = find_palindrome_primes(N)
    print(f"回文质数: {pal_primes}")

if __name__ == "__main__":
    main()

四、素数排列：数字的排列组合

题目：

给定一组数字（如 [1, 2, 3]），生成所有可能的排列，并筛选出其中是质数的排列所组成的整数。

算法思想基础：

• 排列组合：使用递归或 itertools.permutations。
• 质数判断：同上。

实现思路：

1. 生成所有排列。
2. 将排列转为整数。
3. 判断是否为质数，去重后输出。

算法演练：

输入 digits=[1,2,3]，输出：

质数排列: [2, 3, 13, 23, 31]

代码实现：

# filename: prime_permutations.py
from itertools import permutations

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

def prime_permutations(digits):
    """生成所有排列中的质数"""
    perms = set()
    for r in range(1, len(digits)+1):
        for p in permutations(digits, r):
            num = int(''.join(map(str, p)))
            if is_prime(num):
                perms.add(num)
    return sorted(list(perms))

def main():
    digits = [1, 2, 3]
    result = prime_permutations(digits)
    print(f"质数排列: {result}")

if __name__ == "__main__":
    main()

五、亲密数：互为因子的数学缘分

题目：

找出小于N的所有“亲密数对”（a,b），满足 a≠b，且 a的真因子和=b，b的真因子和=a。

算法思想基础：

• 真因子：不包括自身的因子。
• 亲密数定义：σ(a)-a = b 且 σ(b)-b = a，其中σ(n)为因子和函数。

实现思路：

1. 编写 sum_proper_divisors(n) 计算真因子和。
2. 遍历1到N，对每个数a，计算b=sum_proper_divisors(a)。
3. 若b>a且sum_proper_divisors(b)==a，则(a,b)为亲密数对。

算法演练：

输入 N=10000，输出：

亲密数对: [(220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368)]

代码实现：

# filename: amicable_numbers.py
def sum_proper_divisors(n):
    """计算n的真因子和"""
    if n <= 1:
        return 0
    total = 1  # 1总是因子
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            total += i
            if i != n//i:  # 避免平方根重复加
                total += n//i
    return total

def find_amicable_pairs(limit):
    """查找小于limit的亲密数对"""
    pairs = []
    seen = set()
    for a in range(2, limit):
        if a in seen:
            continue
        b = sum_proper_divisors(a)
        if b > a and b < limit:
            if sum_proper_divisors(b) == a:
                pairs.append((a, b))
                seen.add(a)
                seen.add(b)
    return pairs

def main():
    N = 10000
    pairs = find_amicable_pairs(N)
    print(f"亲密数对: {pairs}")

if __name__ == "__main__":
    main()

六、完数：等于自身因子和的数

题目：

找出小于N的所有“完数”（Perfect Number），即其所有真因子之和等于自身。

算法思想基础：

• 完数定义：σ(n) - n = n → σ(n) = 2n。
• 已知完数稀少：6, 28, 496, 8128...

实现思路：

1. 复用 sum_proper_divisors(n)。
2. 遍历1到N，若 sum_proper_divisors(n) == n，则为完数。

算法演练：

输入 N=10000，输出：

完数: [6, 28, 496, 8128]

代码实现：

# filename: perfect_numbers.py
def sum_proper_divisors(n):
    if n <= 1:
        return 0
    total = 1
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            total += i
            if i != n//i:
                total += n//i
    return total

def find_perfect_numbers(limit):
    """查找小于limit的完数"""
    perfects = []
    for n in range(2, limit):
        if sum_proper_divisors(n) == n:
            perfects.append(n)
    return perfects

def main():
    N = 10000
    perfects = find_perfect_numbers(N)
    print(f"完数: {perfects}")

if __name__ == "__main__":
    main()

七、自守数：平方的尾数等于自身

题目：

找出小于N的所有“自守数”（Automorphic Number），即其平方的末尾几位等于它本身。

算法思想基础：

• 自守数示例：5²=25→尾数5；25²=625→尾数25。
• 判断方法：取平方后模10^k（k为原数位数）是否等于原数。

实现思路：

1. 对每个数n，计算n²。
2. 取n的位数k，计算 mod = 10^k。
3. 若 n² % mod == n，则为自守数。

算法演练：

输入 N=1000，输出：

自守数: [1, 5, 6, 25, 76, 376, 625]

代码实现：

# filename: automorphic_numbers.py
def is_automorphic(n):
    """判断是否为自守数"""
    square = n * n
    k = len(str(n))
    mod = 10 ** k
    return square % mod == n

def find_automorphic_numbers(limit):
    """查找小于limit的自守数"""
    result = []
    for n in range(1, limit):
        if is_automorphic(n):
            result.append(n)
    return result

def main():
    N = 1000
    autos = find_automorphic_numbers(N)
    print(f"自守数: {autos}")

if __name__ == "__main__":
    main()

八、多项式运算类的实现

题目：

设计一个 Polynomial 类，支持多项式的加法、减法、乘法、求值、导数等操作。

算法思想基础：

• 多项式表示：系数列表，索引对应幂次。
• 运算规则：按幂次对齐加减，卷积乘法，逐项求导。

实现思路：

1. 初始化：传入系数列表 [a0, a1, a2, ...] 表示 a0 + a1x + a2x² + ...
2. 实现 __add__, __sub__, __mul__。
3. 实现 evaluate(x) 和 derivative()。

算法演练：

输入 p1 = [1, 2, 3] → 1+2x+3x²，p2 = [0, 1] → x
输出：

p1 + p2 = [1, 3, 3] → 1+3x+3x²
p1 * p2 = [0, 1, 2, 3] → x+2x²+3x³
p1'(x) = [2, 6] → 2+6x
p1(2) = 1+4+12=17

代码实现：

# filename: polynomial_class.py
class Polynomial:
    def __init__(self, coefficients):
        # 去除尾部零系数
        while len(coefficients) > 1 and coefficients[-1] == 0:
            coefficients.pop()
        self.coeffs = coefficients or [0]
    
    def __repr__(self):
        terms = []
        for i, c in enumerate(self.coeffs):
            if c == 0:
                continue
            if i == 0:
                terms.append(str(c))
            elif i == 1:
                terms.append(f"{c}x" if c != 1 else "x")
            else:
                terms.append(f"{c}x^{i}" if c != 1 else f"x^{i}")
        return " + ".join(terms) if terms else "0"
    
    def __add__(self, other):
        max_len = max(len(self.coeffs), len(other.coeffs))
        new_coeffs = [0] * max_len
        for i in range(max_len):
            a = self.coeffs[i] if i < len(self.coeffs) else 0
            b = other.coeffs[i] if i < len(other.coeffs) else 0
            new_coeffs[i] = a + b
        return Polynomial(new_coeffs)
    
    def __sub__(self, other):
        max_len = max(len(self.coeffs), len(other.coeffs))
        new_coeffs = [0] * max_len
        for i in range(max_len):
            a = self.coeffs[i] if i < len(self.coeffs) else 0
            b = other.coeffs[i] if i < len(other.coeffs) else 0
            new_coeffs[i] = a - b
        return Polynomial(new_coeffs)
    
    def __mul__(self, other):
        deg1 = len(self.coeffs) - 1
        deg2 = len(other.coeffs) - 1
        new_deg = deg1 + deg2
        new_coeffs = [0] * (new_deg + 1)
        for i, a in enumerate(self.coeffs):
            for j, b in enumerate(other.coeffs):
                new_coeffs[i+j] += a * b
        return Polynomial(new_coeffs)
    
    def evaluate(self, x):
        """霍纳法则求值"""
        result = 0
        for coeff in reversed(self.coeffs):
            result = result * x + coeff
        return result
    
    def derivative(self):
        """求导"""
        if len(self.coeffs) <= 1:
            return Polynomial([0])
        new_coeffs = [i * self.coeffs[i] for i in range(1, len(self.coeffs))]
        return Polynomial(new_coeffs)

def main():
    p1 = Polynomial([1, 2, 3])   # 1 + 2x + 3x^2
    p2 = Polynomial([0, 1])      # x
    
    print("p1 =", p1)
    print("p2 =", p2)
    print("p1 + p2 =", p1 + p2)
    print("p1 * p2 =", p1 * p2)
    print("p1' =", p1.derivative())
    print("p1(2) =", p1.evaluate(2))

if __name__ == "__main__":
    main()

小结

本文通过8道精心设计的算法题，系统性地覆盖了从基础数论到高级数据结构的多项经典数学问题。每道题均包含：

✅ 清晰的题目描述
✅ 深入的算法思想剖析
✅ 详细的实现步骤说明
✅ 可运行的Python代码（含注释）
✅ 实际演练示例

这些内容不仅适合用于博客发表，也可作为教学材料或个人项目实践。更重要的是，它们展示了如何将抽象数学概念转化为具体代码，培养“数学思维+工程实现”的双重能力。

推荐：LeetCode