這個題目應該是比較常見的，本文章將對其進行歸納總結，如有錯誤請各位大佬提出批評
最大公因數，也稱最大公約數、最大公因子，指兩個或多個整數共有約數中最大的一個，a，b的最大公約數記為（a，b），同樣的，a，b，c的最大公約數記為（a，b，c），多個整數的最大公約數也有同樣的記號，求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法，
兩個或多個整數公有的倍數叫做它們的公倍數，其中除0以外最小的一個公倍數就叫做這幾個整數的最小公倍數，整數a，b的最小公倍數記為[a，b]，同樣的，a，b，c的最小公倍數記為[a，b，c]，多個整數的最小公倍數也有同樣的記號，
最小公倍數可以通過兩原數相乘再除以最大公約數得到，
最大公約數和最小公倍數的遍歷求解在此就不再贅述了，
- 輾轉相除法-求最大公約數
#include<stdio.h>
int main()
{
unsigned int a, b;
again:
printf("請輸入兩個原數：");
scanf("%u%u", &a,&b);
unsigned int x = a, y = b;
int c = 0;
if (b == 0)
{
printf("輸入非法，請重輸！");
goto again;
}
while (c = a % b)
{
a = b;
b = c;
}
printf("%d和%d的最大公約數為%d,最小公倍數為%d\n", x, y, b, x*y / b);
return 0;
}
此處求最大公約數也可用函式遞回的的思想
主函式呼叫即可
int fun(int m, int n){
if (n == 0) return m;
return fun(n, m%n);
}
- 迭代法求最小公倍數
#include<stdio.h>
int main()
{
unsigned int a = 0;
unsigned int b = 0;
scanf("%u%u", &a, &b);//防寫負數
int i = 1;
while (a*i%b != 0).//當a*i為b的倍數時肯定也為a的倍數，此時其為最小公倍數
{
i++;
}
printf("%d", a*i);
return 0;
}
- 更相減損術-求最大公約數
int gcd2(int m,int n)
{
int i=0,temp,x;
while(m%2==0&&n%2==0)//判斷m和n能被多少個2整除
{
m/=2;
n/=2;
i+=1;
}
if(m<n)//m保存大的值
{
temp=m;
m=n;
n=temp;
}
while(x)
{
x=m-n;
m=(n>x)?n:x;
n=(n<x)?n:x;
if(n==(m-n))
break;
}
if(i==0)
return n;
else
return (int) pow(2,i)*n;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/271479.html
標籤：其他
下一篇：ASCII編碼表