Pythonプログラムの数値の一意の素因数の積

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

問題の説明

数nが与えられた場合、利用可能なすべての固有の素因数の積を見つけて返す必要があります。

例

Input: num = 11
Output: Product is 11

説明

ここで、入力数は11で、素因数は1つだけで、11です。したがって、それらの積は11です。

アプローチ1

i=2からn+1までのforループを使用して、iがnの因数であるかどうかを確認し、次にiが素数自体であるかどうかを確認します。そうであれば、製品を製品変数に格納し、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))

出力

120

すべての変数の範囲は、下の画像に示されています-

アプローチ2

1）nは2（偶数）で割り切れますが、2を出力し、nを2で割ります。

2）ステップ1の後、nは奇数になる必要があります。ここで、i=3からnの平方根までforループを開始します。 iがnを除算している間に、iを出力し、nをiで除算します。 iがnの除算に失敗した後、iを2でインクリメントし、プロセスを続行します。

3）nが素数で、2より大きい場合、上記の2つのステップでnが1になることはありません。したがって、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

変数のスコープは、下の画像に示されています-

結論

この記事では、ブルートフォースアプローチと効率的なアプローチを使用した、特定の数の一意の素因数の積について学びました。