能夠高效列印給定數字的所有質因子的 C 語言程式？

本節中，我們將瞭解如何高效地獲取某個數字的所有素因數。例如數字 n = 1092，我們需要獲取其所有素因數。1092 的素因數為 2、2、3、7、13。要解決這個問題，我們必須遵循以下規則：

• 如果這個數字能被 2 整除，則列印 2，並將這個數字反覆除以 2。

• 現在這個數字肯定為奇數。現在從 3 到這個數字的平方根，如果數字能被當前的值整除，則列印，然後用當前數字除以這個數字來改變這個數字，然後繼續。

讓我們看一看演算法以獲得更好的思路。

演算法

printPrimeFactors(n)

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

示例

#include<stdio.h>
#include<math.h>
void primeFactors(int n) {
   int i;
   while(n % 2 == 0) {
      printf("%d, ", 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) {
         printf("%d, ", i);
         n = n/i;
      }
   }
   if(n > 2) {
      printf("%d, ", n);
   }
}
main() {
   int n;
   printf("Enter a number: ");
   scanf("%d", &n);
   primeFactors(n);
}

輸出

Enter a number: 24024
2, 2, 2, 3, 7, 11, 13,

阿納布·查克拉博蒂

更新於：2019 年 7 月 30 日

571 次瀏覽

開啟您的 職業

透過完成課程獲得認證

開始