**
用歐幾里得提出的輾轉相除法求兩個數的最大公約數
**可以有兩種想法可以實作此要求
1.可以用短除法找出這兩個自然數的所有公因子，將這些公因子相乘，結果就是這兩個數的最大公約數，例如，48和36的公因子有2、2和3，則48和36的最大公約數是223=12，
代碼如下
#include<stdio.h>
#include"stdlib.h"
int CommFactor1(int m,int n)
{
int i;
int factor=1;
for(i=2;i<=m&&i<-n;i++)
{
while(m%i==0&&n%i==0)
{
factor=factor-i;
m=m/i;
n=n/i;
}
}
return factor;
}
int main()
{
int CommFactor1(int m,int n);
int m,n,number;
printf("請輸入兩個數:");
scanf_s("%d %d",&m,&n);
number=CommFactor1(m,n);
printf("%d和%d的最大公約數為:%d",m,n,number);
return 0;
}
2.采用歐幾里得演算法，其思想是將兩個數輾轉相除直到余數為0，
代碼如下
#include<stdio.h>
#include"stdlib.h"
int CommFactor2(int m,int n)
{
int r=m%n;
while(r!=0)
{
m=n;
n=r;
r=m%n;
}
return n;
}
int main()
{
int CommFactor2(int m,int n);
int m,n,number;
printf("請輸入兩個數:");
scanf_s("%d %d",&m,&n);
number=CommFactor2(m,n);
printf("%d和%d的最大公約數為:%d",m,n,number);
return 0;
}
新手寫的，如有什么錯誤，還請大家指出來
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282581.html
標籤：其他
上一篇：高級程式員都已經優雅的替換掉了“ ! = null ”，你呢？
下一篇：一些最短路的題目