22-11-7学习记录

1，求最大公约数：

   1）辗转相除法：用较大数a   较小数b   a/b=c  --> b/c=d-->  d/c=e......以此类推直到余数为0，最后的除数便是最大公约数

#include<stdio.h>
int gcd(int j, int c)
{
return (j % c == 0) ? c:gcd(c, j % c);
}
int main()
{
int m, n;
scanf("%d%d", &m ,&n);
int  j, k;
j = m; k = n;
if (m < n)
  {
j = n;
k = m;
  }
int ans = gcd(j, k);
printf("最大公因数是:%d\n", ans);
printf("最小公倍数是：%d\n", m * n / ans);
return 0;
  }

2)更相减损法：先判断两个数能否被2整除，若能就除2，不能就用较大数a-较小数b：a-b=c-->

比较b c大小（设b>c），b-c=d-->.....直到差值等于减数（c=d）,此时的差就是最小公因数

#include<stdio.h>
int gcd(int j, int c)
{
while (!(j % 2) && !(c % 2))
  {
j /= 2;
c /= 2;
  }
if (j<c )
  {
int tmp = j;
j = c;
c = tmp;
  }
return (j-c == c) ? c:gcd(j-c,c );
}
int main()
{
int m, n;
scanf("%d%d", &m ,&n);
int  j, k;
j = m; k = n;
int ans = gcd(j, k);
printf("最大公因数是:%d\n", ans);
printf("最小公倍数是：%d\n", m * n / ans);
return 0;
}

3）短除法：找出a  b所有的公因数，相乘既为最大公因数

#include<stdio.h>
int main()
{
int m, n;
int gcd=1, lcm;//gcd:最大公因数是    lcm:最小公倍数是
scanf("%d%d", &m ,& n);

for (int i = 2; i <= m; i ++)
{

if (!(n % i) && !(m % i))
  {
m /= i;
n /= i;
gcd *= i;
i = 1;
  }
}
printf("最大公因数是:%d\n", gcd);
printf("最小公倍数是：%d\n", n* m*gcd);
return 0;

}