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) 的质因数。

让我们看看执行此类操作的以下步骤。

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

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

让我们看看执行此类操作的以下步骤。

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

输出

2
2
2
5
5

解释 -

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

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

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

程序将按以下方式工作。

• 第一步，找到最小的质因数 i。
• 通过反复将 n 除以 i，移除 i 在 n 中的出现。
• 重复上述两个步骤，直到 n 变成 1 或一个质数，其中 n 被 i 除以 i = i + 2。

让我们看另一个例子，其中我们找到给定数字的最大质因数。

示例 - 2 打印给定数字的最大质因数的 Python 程序。

输出

23