Python程式：求一個數的唯一質因數的乘積

在這篇文章中，我們將學習以下問題的解決方案：

問題陳述 - 給定一個數字 n，我們需要找到所有唯一質因數的乘積並返回它。

例如，

Input: num = 11
Output: Product is 11
Explanation:
Here, the input number is 11 having only 1 prime factor and it is 11.
And hence their product is 11.

方法 1

使用 for 迴圈，從 i = 2 到 n+1，檢查 i 是否是 n 的因數，然後檢查 i 本身是否為質數，如果是，則將乘積儲存在 product 變數中，並繼續此過程，直到 I 等於 n。

示例

 線上演示

def productPrimeFactors(n):
   product = 1
   for i in range(2, n+1):
      if (n % i == 0):
         isPrime = 1
         for j in range(2, int(i/2 + 1)):
            if (i % j == 0):
               isPrime = 0
               break
         if (isPrime):
            product = product * i
   return product
# main
n = 18
print (productPrimeFactors(n))

輸出

6

所有變數的作用域如下圖所示：

方法 2

  • 當 n 可以被 2 整除（偶數）時，列印 2 並將 n 除以 2。

  • 步驟 1 之後，n 必須變成奇數。現在從 i = 3 開始一個 for 迴圈，直到 n 的平方根。當 I 可以整除 n 時，列印 I 並將 n 除以 i。當 I 不能整除 n 時，將 I 加 2 並繼續此過程。

  • 如果 n 是一個質數且大於 2，則透過上述兩個步驟，n 不會變成 1。因此，如果 n 大於 2，則列印 n。

示例

import math
def productPrimeFactors(n):
   product = 1
   # prime factor 2
   if (n % 2 == 0):
      product *= 2
      while (n%2 == 0):
         n = n/2
# n must be odd
for i in range (3, int(math.sqrt(n)), 2):
   # While i divides n, print i and
   # divide n
   if (n % i == 0):
      product = product * i
      while (n%i == 0):
         n = n/i
   # n is a prime number greater than 2
   if (n > 2):
      product = product * n
   return product
# main()
n = 8
print (int(productPrimeFactors(n)))

輸出

2

變數的作用域在下面的影像中說明：

結論

在這篇文章中，我們學習瞭如何使用蠻力方法和高效方法來求解給定數字的唯一質因數的乘積。

更新於： 2019年9月11日

1K+ 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告