素因子分解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实现，适用于小于100位的正整数。

import math

def fermat_factorization(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 int(a + math.sqrt(b2)), int(a - math.sqrt(b2))

n = 1234567891011121314151617181920212223242526272829
p, q = fermat_factorization(n)
print(p, q)

在上述代码中，函数`fermat_factorization(n)`接受一个正整数n作为输入，返回n的两个因子p和q。具体实现过程如下：

1. 取a = ceil(sqrt(n))，即向上取整的n开根号的整数部分。
2. 计算b2 = a^2 - n。
3. 如果b2是完全平方数，则返回`int(a + sqrt(b2))`和`int(a - sqrt(b2))`，即n的两个因子。
4. 否则，令a = a + 1，重复步骤2和3，直到找到n的因子为止。

需要注意的是，这种算法仅适用于小于100位的正整数，并且不能保证总是能够找到整数n的因子。因此，在实际应用中，需要使用更高效的因数分解算法，例如Pollard-Rho算法、Quadratic Sieve算法等。

质因子分解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，继续寻找下一个可能的质因数。