好了, 我们继续挑战下Python入门编程, 如何判断一个数是素数？以及如何分解一个合数？

首先回忆下：素数就是大于1且除了1和它本身之外没有其他素因子。大于1的非素数称为合数。形如F_n=2^2^n+1的数称为Fermat数。本节将判断Fermat数是否是素数。

isprime函数

# -*- coding: utf-8 -*-

def isprime(num: int) -> bool:
    if not isinstance(num, int):
        raise TypeError
    if num < 0:
        num = -num
    if num == 1:
        return False
    if num == 2:
        return True
    if not num % 2:
        return False
    p = 3
    while p * p <= num:
        if not num % p:
            return False
        else:
            p += 2
    return True

这里用到了定义函数时, 进行输入参数的类型判断。 想一想, 如何添加输出参数的类型判断。

接下来, 我么将负数转化为正数, 而对1,2这两个特例进行简单处理。最后用一个while循环来从p=3开始判断p是不是其素因子, 如果是则返回非素数, 否则对p+2再次循环判断, 直到p*p超过要判断的数为止。

对Fermat数是否为素数可以测试如下。

# test with Fermat numbers
for i in range(7):
    print(2**2**i + 1, isprime(2**2**i + 1))

素因子分解

从上面可以看到, 对Fermat数F_n=2^2^n+1, F_5, F_6都不是素数。那么我们如何分解它们呢？

def factor(num: int) -> list:
    if not isinstance(num, int):
        raise TypeError
    fl = []
    p = 2
    pl = []
    while p * p <= num:
        # check p is prime or not
        if p in pl or isprime(p):
            if not p in pl:
                pl.append(p)
            if not num % p:
                fl.append(p)
                num = num // p
                # print(p,num)
                factor(num)
            else:
                if p == 2:
                    p += 1
                else:
                    p += 2
        else:
            if p == 2:
                p += 1
            else:
                p += 2
    fl.append(num)
    #print( pl )
    return fl

为了加快程序运行, 我设置了一个pl数组, 记录已经判断过的素数。fl数组用来记录num的素因子。程序用一个while循环来寻找素因子, 首先记录素因子到pl中；而后判断该素因子是不是能够整除num, 如果是整除的, 则将其记录到fl中, 并将num变为商num/p(//返回的是整数), 并递归调用素因子分解函数。

后面两个else有点意思, 其实就是从p=2开始产生新的素数的方法。 如果p=2, 则产生3, 否则产生+2后的素数。

作为测试, 你可以看看20以内的分解。

# simple test of factorization
for i in range(20):
    print(factor(i))

格式化输出

上面的代码, 返回的是形如[2,2,2,3,3,5]素因子数组, 如何将其转换为标准的2^3*3^2*5的形式呢？

def format_factor(lst: list) -> str:
    if not isinstance(lst, list):
        raise TypeError
    dic = {n: lst.count(n) for n in lst}
    formated = ''
    for ek, ev in dic.items():
        if ev == 1:
            formated += str(ek) + '*'
        else:
            formated += str(ek) + '^' + str(ev) + '*'
    # remove last *
    return print(formated[:-1])

其实, 上面的代码可以这样理解。 我们首先将素因子数组lst转化为字典dic, 字典的索引是n, 而对应的值是lst.count(n), 即lst中n的重数。后面的格式化是显然的。只是需要注意这里for循环遍历字典的方法。

作为测试, 你可以试试分解F_5：

format_factor(factor(2**2**5+1))

输出为

641*6700417

最后的思考

上面的素因子分解对F_6感到有点困难了, 你可以试试如何优化代码, 缩短运行时间。