Python 程序：打印给定数质因子

在本教程中，我们将讨论如何使用 Python 程序获得给定数字的质因数。我们所熟悉的质数，如果不是，那么质数就是能被一或自身除的数。例如- 1，2，3，5，7，11，13，…

求一个数的所有素分解

如果用户输入数字 12，那么输出必须是‘2，2，3’，如果输入是 315；输出应该是“3 3 5 7”。程序必须返回给定数的质因数。330 的质因数是 2、3、5 和 11。因此 11 是 330 最重要的质因数。

例如:330 = 2 × 3 × 5 × 11。

在编写 Python 程序之前，我们先来了解以下猜想。

• 1 st 猜想 -在 n 不是质数的情况下，至少可以有一个质因数小于T5√n。

证明- 有两个更大的 sqrt(n) 数，那么它们的乘积也应该除 n，但会超过 n，这与我们的假设相矛盾。所以 n 的质因数不能超过 sqrt(n)。

让我们看下面的步骤来执行这样的操作。

p <= sqrt(n} or q <= sqrt(n)

• 22猜想- 可以有 n 大于 sqrt(n)的 AT-MOST 1 质因子。

证明- 假设有两个更大的 sqrt(n) 数，那么它们的乘积也应该除以 n，但将超过 n，这与我们的假设相矛盾。所以 n 的质因数不能大于 1sqrt(n)。

让我们看下面的步骤来执行这样的操作。

示例-打印质因数的 Python 程序

import math
# Below function will print the
# all prime factor of given number
def prime_factors(num):
    # Using the while loop, we will print the number of two's that divide n
    while num % 2 == 0:
        print(2,)
        num = num / 2

    for i in range(3, int(math.sqrt(num)) + 1, 2):

        # while i divides n , print i ad divide n
        while num % i == 0:
            print(i,)
            num = num / i
    if num > 2:
        print(num)
# calling function 

num = 200
prime_factors(num)

输出:

2
2
2
5
5

解释-

在上面的代码中，我们已经导入了math模块。质因数()功能是负责打印合成数。首先，我们得到偶数；在此之后，所有剩余的质因数一定是奇数。在 for循环中，数字必须是奇数，所以我们将 I 加 2。for循环将运行 n 次的平方根。

让我们理解复合数的下列性质。

每个合成数至少有一个小于或等于平方根的质因数。T3】

该程序将按如下方式工作。

• 第一步，找到最小质因数 I。
• I 的出现将通过重复 n 除以 I 而从 n 中去除。
• 重复上述两个步骤来划分 n 和 i = i + 2。这两个步骤将重复进行，直到 n 变成 1 或质数。

让我们理解另一个例子，在这个例子中，我们找到了给定数的最大质因数。

例- 2 Python 程序求给定数的最大质因数。

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

print(largest_prime_factor(345))

输出:

23