有哪些因數 (十) - 求最大公因數 (輾轉相除法)
本帖最後由 鄭繼威 於 2022-9-28 20:08 編輯
試以輾轉相除法，解最大公因數。- #include<iostream>
- #include<cstdlib>
- using namespace std;
- int main()
- {
- re:
- int x,y,tmp;
- cout<<"請依序輸入兩個正整數: ";
- cin>>x>>y;
- cout<<x<<"與"<<y<<"的最大公因數為: ";
- //看到0才代表輾轉相除法結束
- while(x%y!=0)
- {
- //一直交換
- tmp=x%y;
- x=y;
- y=tmp;
- }
- cout<<y<<endl<<endl;
- goto re;
- system("pause");
- return 0;
- }
- /*
- x y
- 35 / 56 = 0 ... 35
- 56 / 35 = 1 ... 21
- 35 / 21 = 1 ... 14
- 21 / 14 = 1... 7
- 14 / 7 = 2 ... 0
- */
|
