2019年11月7日 星期四

【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基金會的贊助。
您只需要支持我們,完全不會花到錢!