Python
 Computer >> コンピューター >  >> プログラミング >> Python

数の最大の素因数を見つけるためのPythonプログラム

この記事では、以下に示す問題ステートメントの解決策について学習します-

問題の説明

正の整数nが与えられます。数の最大の素因数を見つける必要があります。

アプローチ

  • 指定された数値を数値の約数で割って因数分解します。
  • 最大素因数を更新し続けます。

例

import math
def maxPrimeFactor(n):
   # number must be even
   while n % 2 == 0:
      max_Prime = 2
      n /= 1
   # number must be odd
   for i in range(3, int(math.sqrt(n)) + 1, 2):
      while n % i == 0:
         max_Prime = i
         n = n / i
   # prime number greator than two
   if n > 2:
      max_Prime = n
   return int(max_Prime)
# Driver code to test above function
n = 15
print(maxPrimeFactor(n))

時間計算量：O（n ^½）

補助スペース：O（1）

出力

5

次の図に示すように、すべての変数はグローバルフレームで宣言されます。

数の最大の素因数を見つけるためのPythonプログラム

結論

この記事では、数の最大の素因数を見つける方法について学びました


  1. 数の因子の最小合計を見つけるためのPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します- 問題の説明 入力された数値を指定して、指定された数値の因子の最小合計を求めます。 ここでは、すべての因子とそれに対応する合計を計算し、それらの中から最小値を見つけます。 したがって、数の積の最小合計を見つけるために、積の素因数の合計を見つけます。 これが問題の反復実装です- 例 #iterative approach def findMinSum(num):    sum_ = 0    # Find factors of number and add to the sum

  2. 数の一意の素因数の積のための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 i=2からn+1までのforループを使用して、iがnの因数であるかどうかを確認し、次に