輾轉相除法__約分

#include<iostream>
using namespace std;
int main()
{

    int temp1;
    int temp2;
    cin>>temp1>>temp2;

    int a=temp1;

    int b=temp2;

        while(b!=0)
        {
        int temp=a%b;
        a=b;
        b=temp;

        }

    cout<<temp1/a<<"/"<<temp2/a;
  return 0;
}      

輾轉相除法

輾轉相除法：輾轉相除法是求兩個自然數的最大公約數的一種方法，也叫歐幾裡德算法。

例如，求（319，377）：

∵ 319÷377=0（餘319）

∴（319，377）=（377，319）；

∵ 377÷319=1（餘58）

∴（377，319）=（319，58）；

∵ 319÷58=5（餘29）

∴ （319，58）=（58，29）；

∵ 58÷29=2（餘0）

∴ （58，29）= 29；

∴ （319，377）=29。