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

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

• 数値が2で割り切れる場合は、2を最大として格納し、数値を2で繰り返し除算します。

• 今、数は奇数でなければなりません。ここで、数値の3から平方根まで、数値が現在の値で割り切れる場合は、係数を最大値として格納し、数値を現在の数値で割って変更してから続行します。

• そして最後に、数値が2より大きい場合、それは1ではないので、最大素因数を取得します。

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

アルゴリズム

getMaxPrimeFactors（n）

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

例

#include<stdio.h>
#include<math.h>
int getMaxPrimeFactor(int n) {
   int i, max = -1;
   while(n % 2 == 0) {
      max = 2;
      n = n/2; //reduce n by dividing this by 2
   }
   for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get
      only odd numbers
      while(n % i == 0) {
         max = i;
         n = n/i;
      }
   }
   if(n > 2) {
      max = n;
   }
   return max;
}
main() {
   int n;
   printf("Enter a number: ");
   scanf("%d", &n);
   printf("Max prime factor: %d", getMaxPrimeFactor(n));
}

出力

Enter a number: 24024
Max prime factor: 13