Python教程-Python程序打印给定数字的质因数

在本教程中，我们将讨论如何使用Python程序获取给定数字的质因数。我们都熟悉质数，如果不了解，那么质数是只能被1或自己整除的数字。例如 - 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程序之前，让我们了解以下猜想。

• 第一个猜想 - 在n不是质数的情况下，至少会有一个小于√n的质因数。

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

让我们看看执行这种操作的以下步骤。

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

• 第二个猜想 - n最多有1个大于sqrt(n)的质因数。

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

让我们看看执行这种操作的以下步骤。

示例 - 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模块。prime_factors()函数负责打印复合数字。首先，我们得到偶数；在此之后，所有剩下的质因数必须是奇数。在for循环中，num必须是奇数，所以我们以2递增i。for循环将运行n的平方根次数。

让我们了解复合数的以下属性。

每个复合数都至少有一个小于或等于平方根的质因数。

程序将按如下方式工作。

• 第一步，找到最小的质因数i。
• 通过反复将n除以i，去除i的出现。
• 重复上述两个步骤，直到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