Python算法探秘：用代码解决经典数学问题

在编程学习中，将数学问题与算法实现相结合，是提升编程能力的绝佳途径。今天，让我们一起探索几个用Python解决经典数学问题的有趣案例，感受算法思维与数学之美的碰撞。

一、哥德巴赫猜想的并行验证

哥德巴赫猜想提出：任一大于2的偶数都可以写成两个质数之和。虽然这个猜想尚未被严格证明，但我们可以用计算机在有限范围内验证它。

import math
from multiprocessing import Pool, cpu_count

def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def GDBH(T):
    S, E = T[0], T[1]
    S = max(4, S)
    if S % 2 == 1:
        S += 1
    
    for i in range(S, E + 1, 2):
        isGDBH = False
        for j in range(i // 2 + 1):
            if isPrime(j) and isPrime(i - j):
                isGDBH = True
                if i % 100000 == 0:
                    print(f'{i}={(j)}+{(i-j)}')
                break
        if not isGDBH:
            print('哥德巴赫猜想失败！！')
            break

亮点：使用多进程技术将大数区间分段并行处理，充分发挥多核CPU性能，大幅提升验证效率。

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

寻找质数是数论中的基础问题，埃拉托色尼筛法是一种经典的质数筛选算法：

def findAllPrime(n):
    pt = [True] * n
    prime = []
    
    for p in range(2, n):
        if not pt[p]:
            continue
        prime.append(p)
        for i in range(p * p, n, p):
            pt[i] = False
    
    return prime, pt

进阶应用：基于这个筛法，我们可以寻找等差质数序列：

prime, pt = findAllPrime(100)
for i in range(len(prime)):
    for j in range(i + 1, len(prime)):
        a0, a1 = prime[i], prime[j]
        an = a1 + a1 - a0
        s = []
        while an < 100 and pt[an]:
            s.append(an)
            an += a1 - a0
        if s:
            print([a0, a1] + s)

三、回文质数：对称之美

回文数是指从左向右读和从右向左读都一样的数，兼具回文特性和质数特性的数更是数学中的珍品：

import math

def isPrimeNumber(num):
    i = 2
    x = math.sqrt(num)
    while i < x:
        if num % i == 0:
            return False
        i += 1
    return True

def Reverse(num):
    rNum = 0
    while num:
        rNum = rNum * 10 + num % 10
        num //= 10
    return rNum

def RPrimeNumber(num):
    arr = []
    i = 2
    while i < num:
        if isPrimeNumber(i) and i == Reverse(i):
            arr.append(i)
        i += 1
    return arr

print(RPrimeNumber(1000))

另一种巧妙解法：利用字符串反转和质数表，寻找可逆质数对：

def getPrimeTable(n):
    pt = [True] * n
    for p in range(2, n):
        if not pt[p]:
            continue
        for i in range(p * p, n, p):
            pt[i] = False
    return pt

pt = getPrimeTable(900)
for p in range(10, 900):
    if not pt[p]:
        continue
    q = int(str(p)[::-1])
    if p != q < 900 and pt[q]:
        pt[q] = False
        print(p, q)

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

从特定数字集合中选取部分数字组成新数，并判断其是否为质数，这是一个有趣的组合数学问题：

import math
from itertools import permutations
from functools import reduce

def isPrimeNum(n):
    for k in range(2, int(math.sqrt(n) + 1)):
        if n % k == 0:
            return False
    return True

for p in permutations([1, 3, 5, 7, 9], 5):
    for l in (p[1:-1], p[::2], p):
        s = reduce(lambda x, y: 10 * x + y, l)
        if not isPrimeNum(s):
            break
    else:
        print(p)

这段代码在探索：哪些由奇数数字组成的排列中，其中间部分、奇数位和全部数字组成的数都是质数？

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

亲密数是指两个不同的正整数，其中每个数的所有真因子之和等于另一个数：

def check(n):
    s = 0
    for i in range(1, int(n / 2) + 1):
        if n % i == 0:
            s += i
    return s

for i in range(1, 3000):
    res = check(i)
    if i != res and check(res) == i:
        print(i, res)

运行结果将输出如(220, 284)这样经典的亲密数对。

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

完数是指所有真因子之和恰好等于自身的数：

def approximateNumber(num):
    result = []
    for divisor in range(1, num):
        temp = []
        for dividend in range(1, divisor):
            if divisor % dividend == 0:
                temp.append(dividend)
        if sum(temp) == divisor:
            result.append(divisor)
    return result

print(approximateNumber(1000))  # 输出：[6, 28, 496]

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

自守数是指一个数的平方的末尾几位等于这个数本身：

print([n for n in range(1, 10000) 
       if n * n % (10 ** len(str(n))) == n])

短短一行代码，就能找出1到10000之间的所有自守数。

八、最大公约数与最小公倍数

经典的辗转相除法（欧几里得算法）求解最大公约数：

m = int(input("请输入一个正整数："))
n = int(input("请输入第二个正整数："))
a, b = m, n

if a > b:
    a, b = b, a
    
while a != 0:
    r = b % a
    b = a
    a = r
    
max_div = b
min_mul = m * n // max_div
print(f"{m}和{n}的最大公约数是{max_div}，最小公倍数是{min_mul}")

九、多项式运算类的实现

面向对象的方式实现多项式的加减乘运算：

class poly:
    __a = [0]*20
    __b = [0]*20
    __result = [0]*20
    
    def __add(self, a, b):
        return [a[i]+b[i] for i in range(20)]
    
    def __minus(self, a, b):
        return [a[i]-b[i] for i in range(20)]
    
    def __mul(self, a, b):
        self.__result = [0]*20
        for i in range(10):
            for j in range(10):
                self.__result[i+j] += a[i] * b[j]
        return self.__result
    
    def __output(self, a):
        b = ''
        for i in range(20):
            if a[i] > 0:
                b += '+' + str(a[i]) + 'X^' + str(i)
            if a[i] < 0:
                b += '-' + str(-a[i]) + 'X^' + str(i)
        print(b[1::])
    
    def control(self):
        print("二项式运算：\n")
        self.__Input(self.__a)
        while True:
            operator = input('请输入运算符（结束运算请输入‘#’）')
            if operator == '#':
                return 0
            else:
                self.__b = [0]*20
                self.__Input(self.__b)
                self.__a = {'+': self.__add(self.__a, self.__b),
                           '-': self.__minus(self.__a, self.__b),
                           '*': self.__mul(self.__a, self.__b)}.get(operator)
                print('计算结果：', end='')
                self.__output(self.__a)

十、字母算式穷举：wwwdot - google = dotcom

最后一个案例展示了如何用穷举法解决字母算式谜题，每个字母代表一个不同的数字：

import os
import time
from datetime import datetime

class data_struct():
    def __init__(self, letter, status):
        self.letter = letter
        self.status = status
        if self.status == False:
            self.digit = list(range(10))
        else:
            self.digit = list(range(1, 10))

def norepeat(list0):
    return len(set(list0)) == len(list0)

if __name__ == '__main__':
    '''wwwdot - google = dotcom'''
    letterW = data_struct('W', True)
    letterG = data_struct('G', True)
    letterD = data_struct('D', True)
    letterO = data_struct('O', False)
    letterT = data_struct('T', False)
    letterL = data_struct('L', False)
    letterE = data_struct('E', False)
    letterC = data_struct('C', False)
    letterM = data_struct('M', False)
    
    begintime = datetime.now()
    for w in letterW.digit:
        for g in letterG.digit:
            for d in letterD.digit:
                for o in letterO.digit:
                    for t in letterT.digit:
                        for l in letterL.digit:
                            for e in letterE.digit:
                                for c in letterC.digit:
                                    for m in letterM.digit:
                                        list0 = [w, g, d, o, t, l, e, c, m]
                                        if norepeat(list0):
                                            str1 = str(w)*3 + str(d) + str(o) + str(t)
                                            str2 = str(g) + str(o)*2 + str(g) + str(l) + str(e)
                                            str3 = str(d) + str(o) + str(t) + str(c) + str(o) + str(m)
                                            if int(str1) - int(str2) == int(str3):
                                                print(str1, str2, str3)
    endtime = datetime.now()
    print('穷举搜索耗时：', endtime - begintime)

这个算法使用9层循环穷举所有可能的数字组合，寻找满足等式wwwdot - google = dotcom的解。

结语

通过以上案例，我们不仅回顾了经典的数学问题，还学习了如何用Python实现各类算法：从简单的暴力穷举到高效的筛法，从单线程到多线程并行计算，从面向过程到面向对象的设计思想。

这些代码展示了计算机科学如何帮助我们探索数学世界的奥秘，也为我们提供了宝贵的算法思维训练。希望这些案例能激发你对算法和数学的兴趣，在实际编程中创造出更多精彩的解决方案！