Python实现正整数分解质因数操作示例

Python实现正整数分解质因数的操作示例

在数学中，正整数可以分解成若干个质数的积的形式，称为正整数的质因数分解。本文将使用 Python 语言实现正整数分解质因数的操作。实现过程分为两部分：一、编写判断质数函数；二、质因数分解。

判断质数函数

质数的定义是只有 1 和本身两个因数的自然数，因此判断一个数是不是质数，只需要循环判断从 2 开始到自己的平方根之间的所有数是否能整除即可。

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

质因数分解

质因数分解的过程是将一个正整数不断分解成若干个质数乘积的形式，直到无法继续分解为止。首先判断输入的数是否为质数，如果是质数则输出自身即可；如果不是质数，将其分解成若干个质数乘积即可。

def prime_factors(num):
    factors = []
    for i in range(2, num+1):
        if is_prime(i):
            while num % i == 0:
                factors.append(i)
                num //= i
        if num == 1:
            break
    return factors

示例说明

示例一

输入一个正整数 12，经过函数运算得到它的质因数分解为 2 x 2 x 3。

>>> print(prime_factors(12))
[2, 2, 3]

示例二

输入一个正整数 465，经过函数运算得到它的质因数分解为 3 x 5 x 31。

>>> print(prime_factors(465))
[3, 5, 31]

通过上述两个示例，我们可以看到程序输出的质因数分解结果是正确的。同时，我们还可以使用其他正整数进行测试，验证函数的正确性。