质因数分解最优解 python

质因数分解是将一个正整数分解成为几个质数的乘积的过程，可以使用Python编写一个最优解来进行质因数分解。

首先，我们可以编写一个函数来判断一个数字是否为质数。判断方法可以是从2开始，逐个除以小于其开方的数，如果能够整除，则不是质数；如果无法整除，则是质数。

接下来，我们可以编写一个函数来进行质因数分解。该函数的输入是一个正整数，输出是该数的所有质因数。方法是从2开始，如果能够整除，则将该数除以该因数，再次从2开始进行除法运算，直到该数不能再被整除为止。

下面是一个质因数分解的最优解Python代码示例：

import math

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

# 质因数分解
def prime_factorization(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n = n // 2
    i = 3
    while i <= math.sqrt(n):
        while n % i == 0:
            factors.append(i)
            n = n // i
        i += 2
    if n > 2:
        factors.append(n)
    return factors

# 测试
n = int(input("请输入一个正整数："))
if is_prime(n):
    print("{}是一个质数".format(n))
else:
    prime_factors = prime_factorization(n)
    print("{}的质因数分解为：".format(n), prime_factors)

以上代码中，`is_prime`函数用于判断一个数是否为质数，`prime_factorization`函数用于进行质因数分解。在Main函数中，首先输入一个正整数并进行判断，如果是质数则输出结果，如果不是质数则进行质因数分解并输出结果。

这个最优解的质因数分解算法的时间复杂度约为O(sqrt(n))，其中n为待分解的数。