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程序之前，让我们先了解一下以下推测。

第1个猜想 - 如果n不是素数，则至少有一个素数因子小于 √n 。
证明 – 如果存在两个大于 sqrt(n) 的数字，那么它们的乘积也应该能够整除n，但这将超过n，这与我们的假设相矛盾。因此，n的大于 sqrt(n) 的素数因子不可能超过一个。

让我们看看执行这样一个操作的步骤。

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

第2猜想 – n最多只能有一个大于sqrt(n)的质因子。

证明 – 假设有两个大于sqrt(n)的数，它们的乘积也应该能整除n，但它们将超过n，这与我们的假设相矛盾。因此，n最多只能有一个大于sqrt(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)

输出：

解释-

在上面的代码中，我们导入了math模块。prime_factor()函数负责打印复合数。首先，我们得到偶数；在此之后，所有剩余的质因数必须是奇数。在for循环中，num必须是奇数，所以我们将i增加2。for循环将运行n的平方根次数。

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

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

该程序将按照以下方式工作。

步骤1，找到最小的质因数i。
通过反复除以i来从n中删除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))

输出：