数の一意の素因数の積を見つけるためのC/C ++プログラム？

このセクションでは、数値の一意の素因数の積を効率的な方法で取得する方法を説明します。 n =1092と言う数があり、これの一意の素因数の積を取得する必要があります。 1092の素因数は2、2、3、7、13です。したがって、一意の素因数は{2、3、7、13}であり、積は546です。この問題を解決するには、この規則に従う必要があります-

• 数値が2で割り切れる場合は、2に積を掛け、数値を2で繰り返し除算すると、次の2は無視されます。

• 今、数は奇数でなければなりません。ここで、数値の3から平方根まで、数値が現在の値で割り切れる場合は、係数を積に乗算し、数値を現在の数値で除算して変更し、続行します。次は上記のように無視されます

• そして最後に、数が2より大きい場合は、1ではないので、残りの数を掛けます。

より良いアイデアを得るためのアルゴリズムを見てみましょう。

アルゴリズム

uniquePrimeProduct（n）

begin
   prod := 1
   if n is divisible by 2, then
      prod := prod * 2
      n := n / 2
   end if
   while n is divisible by 2, do
      n := n / 2
   done
   for i := 3 to √𝑛, increase i by 2, do
      if n is divisible by i, then
         prod := prod * i
         n := n / i
      end if
      while n is divisible by i, do
         n := n / i
      done
   done
   if n > 2, then
      prod := prod * n
   end if
end

例

#include<stdio.h>
#include<math.h>
int uniquePrimeProduct(int n){
   int i, prod = 1;
   if(n % 2 == 0){
      prod *= 2;
      n = n/2;
   }
   while(n % 2 == 0){//skip next 2s
      n = n/2;
   }
   for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers
      if(n % i == 0){
         prod *= i;
         n = n/i;
      }
      while(n % i == 0){ //skip next i's
         n = n/i;
      }
   }
   if(n < 2){
      prod *= n;
   }
   return prod;
}
main() {
   int n;
   printf("Enter a number: ");
   scanf("%d", &n);
   printf("Product of prime factors: %d", uniquePrimeProduct(n));
}

出力

Enter a number: 1092
Product of prime factors: 546