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;      

}