【C語言】求兩數的最大公因數（質因數分解）

以最簡單的方式，用C語言的if、while，完成質因數分解，求出兩正整數的最大公因數。

輸入

#include <stdio.h>

int main()
{
     int a,b; 
     int ans=1; //起始數為1
     int i=2; //質因數分解由2開始
     scanf("%d %d",&a,&b); 

     //若a、b小於2，不計算
     if( a==1 || b==1 ) printf("1");
     if( a==0 || b==0 ) printf("0");
     else if( a>=i && b>=i )
     {
          //a,b皆大於等於2時，開始質因數分解 
          while( a>=i && b>=i ) 
          { 
               //餘數皆為0時，2開始質因數分解，若皆被2分完，則陸續增加為3、4、5…… 
               while( a%i==0 && b%i==0 ) 
               { 
                    ans = ans * i; 
                    a /= i; 
                    b /= i; 
               } 
               i++; 
          } 
          printf("%d",ans); 
     }
     else printf("Error\n");
     return 0;
}

輸出

例題一：

12 16
4

例題二：

1 8
1

例題三：

23 0
0

👉【幫我們一個忙！】👈

👋如果您喜歡這篇文章，請在下方按5個Like！

 ❤您的支持是我們最大的動力！

您只要登入帳號（Facebook、Google），在下方按5個Like，我們就會收到來自LikeCoin基金會的贊助。

您只需要支持我們，完全不會花到錢！