素因子分解python

以下是一个用Python实现的素因子分解的例子：

def prime_factorization(n):
    factors = []
    p = 2
    while n > 1:
        if n % p == 0:
            factors.append(p)
            n //= p
        else:
            p += 1
    return factors

number = 36
result = prime_factorization(number)
print("Prime factors of", number, "are:", result)

这个例子中，我们定义了一个函数`prime_factorization`来进行素因子分解。我们使用一个循环来不断除以最小的素数，直到被分解的数变为1。如果当前的素数是被分解数的因子，我们将其添加到结果列表中，并将被分解数除以该素数。如果当前的素数不是被分解数的因子，我们将素数加1，继续下一轮循环。最后，我们返回结果列表。

在上面的例子中，我们对数字36进行素因子分解，得到的结果是[2, 2, 3, 3]，表示36可以分解为2 * 2 * 3 * 3。

相关问题

费马因子分解python

费马因子分解是一种用于将一个大合数分解为其质因数的算法。以下是一个使用Python实现费马因子分解的示例代码：

import math

def fermat_factor(n):
    a = math.ceil(math.sqrt(n))
    b2 = a*a - n
    while not math.sqrt(b2).is_integer():
        a += 1
        b2 = a*a - n
    return (a - math.isqrt(b2), a + math.isqrt(b2))

n = 123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789
print(fermat_factor(n))

在上面代码中，我们首先导入了Python内置的math库。然后我们定义了一个名为`fermat_factor`的函数，它接收一个整数`n`作为输入，并返回一个包含`n`的质因数的元组。算法的实现基于费马小定理和勾股定理，它通过逐步增加`a`的值并计算`b2 = a*a - n`来找到满足`b2`是完全平方数的整数`a`。最后，函数返回`(a - isqrt(b2), a + isqrt(b2))`作为`n`的因数。

在上面的示例代码中，我们使用了一个非常大的数`n`进行测试，这可能需要一些时间才能得到结果。

质因子分解python

以下是一个Python实现的质因数分解函数示例：

def prime_factors(n):
    factors = []
    i = 2
    while i <= n:
        if n % i == 0:
            factors.append(i)
            n /= i
        else:
            i += 1
    return factors

# 测试函数
num = int(input("请输入一个正整数："))
result = prime_factors(num)
print(f"{num}的质因数分解为：{result}")

该函数接受一个正整数作为参数，返回一个列表，其中包含该数的所有质因数。函数使用了一个简单而有效的算法，从最小的质数2开始，依次判断该数是否能被当前的数整除。如果能整除，说明找到了一个质因数，将其添加到factors列表中，并将该数除以该质因数，以继续寻找下一个质因数。如果不能整除，将当前数加1，继续寻找下一个可能的质因数。