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 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