在本教程中，我们将讨论如何使用 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
原创文章，作者：RAAGF，如若转载，请注明出处：https://www.506064.com/n/324654.html
微信扫一扫 
支付宝扫一扫 