辗转相除法求两个正整数的最大公约数

      该算法的要领是：假设两个正整数为a和b，先求出前者除以后者的余数，存放到变量r中，若r不为0，则将b的值得赋给a，将r的值得赋给b；再求出a除以b的余数，仍然存放到变量r中……如此反复，直至r为0时终止，此时b中存放的即为原来两数的最大公约数。

1、任意读入两个正整数，求出它们的最大公约数。

[法一：用while循环时，最大公约数存放于b中]

#include  "stdio.h "

void main()
{
 int a,b,r;
 do  
     scanf("%d%d",&a,&b);
 while(a<=0||b<=0);      /*确保a和b为正整数*/
 r=a%b;
 while(r!=0)
  {
    a=b;
    b=r;
    r=a%b;
  }
 printf("%d\n",b);
}  

[法二：用do…while循环时，最大公约数存放于a中]

#include  "stdio.h "

void main()
{
 int a,b,r;
 do  
   scanf("%d%d",&a,&b);
 while(a<=0||b<=0);  /*确保a和b为正整数*/
 do 
   {
   r=a%b;
   a=b;
   b=r;
   }while(r!=0);
 printf("%d\n",a);
}

【引申】可以利用最大公约数求最小公倍数。提示：两个正整数a和b的最小公倍数=a×b/最大公约数。

2、任意读入两个正整数，求出它们的最小公倍数。

[法一：利用最大公约数求最小公倍数]

#include  "stdio.h "

void main()
{
 int a,b,r,x,y;
 do  
   scanf("%d%d",&a,&b);
 while(a<=0||b<=0);  /*确保a和b为正整数*/
 x=a; 
 y=b;           /*保留a、b原来的值*/
 r=a%b;
 while(r!=0) {a=b;b=r;r=a%b;}
 printf("%d\n",x*y/b);
}

 [法二：若其中一数的最小倍数也是另一数的倍数，该最小倍数即为所求]

#include  "stdio.h "

void main()
{
 int a,b,r,i;
 do  
   scanf("%d%d",&a,&b);
 while(a<=0||b<=0);  /*确保a和b为正整数*/
   i=1;
 while(a*i%b!=0) 
   i++;
 printf("%d\n",i*a);
}

[法三：输入两个正整数m和n，求其最大公约数和最小公倍数。

#include  "stdio.h "

void main()
{ 
  int a,b,num1,num2,temp;
  printf("please input two numbers:\n");
  scanf("%d,%d",&num1,&num2);
  if(num1 { 
    temp=num1;
    num1=num2;
    num2=temp;
  }
  a=num1;
  b=num2;
  while(b!=0)              /*利用辗除法，直到b为0为止*/
    {
      temp=a%b;
      a=b;
      b=temp;
     }
  printf("gongyueshu:%d\n",a);
  printf("gongbeishu:%d\n",num1*num2/a);
}

法四Algorithm Gossip: 最大公因数、最小公倍数、因式分解

 说明最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求：

GCD * LCM = 两数乘积

解法最大公因数可以使用递回与非递回求解，因式分解基本上就是使用小于输入数的数值当作除数，去除以输入数值，如果可以整除就视为因数，要比较快的解法就是求出小于该数的所有质数，并试试看是不是可以整除

实作（最大公因数、最小公倍数）

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int m, n, r;
    int s;
    printf("输入两数：");
    scanf("%d %d", &m, &n);
    s = m * n;
 
    while(n != 0) {
        r = m % n;
        m = n;
        n = r;
    }
    printf("GCD：%d\n", m);
    printf("LCM：%d\n", s/m);
 
    return 0;
}

实作（因式分解）

 C（不用质数表）

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int i, n;
    printf("请输入整数：");
    scanf("%d", &n);
    printf("%d = ", n);
    for(i = 2; i * i <= n;) {
        if(n % i == 0) {
            printf("%d * ", i);
            n /= i;
        }
        else
            i++;
    }
    printf("%d\n", n);
    return 0;
}

C（使用质数表）

#include <stdio.h>
#include <stdlib.h>
#define N 1000

int prime(int*);  // 求质数表
void factor(int*, int);  // 求factor


int main(void) {
    int ptable[N+1] = {0};
    int count, i, temp;
    count = prime(ptable);
    printf("请输入一数：");
    scanf("%d", &temp);
    factor(ptable, temp);
    printf("\n");
    return 0;
 }
 
 int prime(int* pNum) {
    int i, j;
    int prime[N+1];
    for(i = 2; i <= N; i++)
        prime[i] = 1;
 
    for(i = 2; i*i <= N; i++) {
        if(prime[i] == 1) {
            for(j = 2*i; j <= N; j++) {
                if(j % i == 0)
                    prime[j] = 0;
            }
        }
    }
 
    for(i = 2, j = 0; i < N; i++) {
        if(prime[i] == 1)
            pNum[j++] = i;
    }
    return j;
}
void factor(int* table, int num) {
    int i;
    for(i = 0; table[i] * table[i] <= num;) {
        if(num % table[i] == 0) {
            printf("%d * ", table[i]);
            num /= table[i];
        }
        else
            i++;
    }
    printf("%d\n", num);
}