C语言巧用辗转相除法求两个正整数的最大公约数

Jack20 发表于 2021/03/02 19:27:55 2021/03/02
【摘要】 辗转相除法求两个正整数的最大公约数      该算法的要领是:假设两个正整数为a和b,先求出前者除以后者的余数,存放到变量r中,若r不为0,则将b的值得赋给a,将r的值得赋给b;再求出a除以b的余数,仍然存放到变量r中……如此反复,直至r为0时终止,此时b中存放的即为原来两数的最大公约数。1、任意读入两个正整数,求出它们的最大公约数。[法一:用while循环时,最大公约数存放于b中]#inc...

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

      该算法的要领是:假设两个正整数为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);
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。