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。猜想 - 当 n 不是素数时，至少可以有一个小于 T5√n 的素数。

证明 - 有两个较大的 sqrt(n) 数字，因此它们的乘积也将被 n 整除，但会超过 n，这与我们的假设相矛盾。所以n的质因数不能超过sqrt(n)。

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

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

• 22 猜想 - 至少可以有 1 个 n 大于 sqrt(n) 的质因数。

证明 - 假设有两个较大的 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。 primefactor() 函数负责打印合数。首先我们得到一个偶数；之后，所有剩余的质因数都必须是奇数。在 for 循环中，数字必须是奇数，因此我们将 2 添加到 I。 for 循环将运行 n 次的平方根。

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

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

该程序将按如下方式运行。

• 第一步是找到最小的质因数 I。
通过重复将 n 除以 I，
• 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

---