C语言求两个数中最大公约数

在C语言中如何求两个数的最大公约数呢?下面用三种方法进行求解。

方法一:穷举法。

先比较两个数的大小,然后找出较小数t,最后判断t为何值时两个数都能整除,此方法效率较低。

代码如下:

#include<stdio.h>
int main()
{
     int num1,num2,temp,i;
     scanf("%d%d",&num1,&num2);
     if(num1>num2)
     {
           temp=num1;
           num1=num2;
           num2=temp;
      }/*将较小值赋给num1*/
     for(i=num1;i>0;i--)
     {
           if(num1%i==0&&num2%i==0)/*两个数都被i整除时即为最大公约数*/
           printf("%d ",i);
      }
return 0;
}

方法二:辗转相减法。

辗转相减法是用较大数减去较小数,再比较减数和差的大小,用较大数减去较小数,如此不断循环,直到两数相减为0停止,则最大公约数就求出来了。

代码如下:

#include<stdio.h>
int main()
{
      int a,b;
      scanf("%d%d",&a,&b);
      while(a!=b)
      {
          if(a>b)a=a-b;/*比较两数大小,大数减小数差并赋给a*/
          else b=b-a;
       }
      printf("%d",b);
return 0;
}

方法三:辗转相除法。

辗转相除法求两个数的最大公约数的步骤如下:

先用小的一个数除大的一个数,得第一个余数;

再用第一个余数除小的一个数,得第二个余数;

又用第二个余数除第一个余数,得第三个余数;
        这样逐次用后一个数去除前一个余数,直到余数是0为止.那么,最后一个除数就是所求的最大公约数(如果最后的除数是1,那么原来的两个数是互质数。)

代码如下:

#include<stdio.h>
int main()
{
      int num1,num2,temp;
      scanf("%d%d",&num1,&num2);
      /*不需要判断两个数的大小,当num1<num2时,在经过一次运算后,两个数自动进行交换。*/
      while(num2)
      {
            temp=num1%num2;/*辗转相除求最大公约数*/
            num1=num2;
            num2=temp;
       }
       printf("%d",num1);
return 0;
}

最小公倍数求法:要求的两个数相乘除以最大公约数就是两个数的最小公倍数。

时间: 09-30

C语言求两个数中最大公约数的相关文章

C语言--求两个数的最大公约数

问题: 求两个数的最大公约数 #include<stdio.h> #include<math.h>  main() { int a,b,c,i,j; printf("请输入三个数(数以逗号隔开):\n"); int arr[3]; int t; scanf_s("%d,%d,%d", &a,&b,&c); arr[0] = a;  arr[1] = b;  arr[2] = c; for (j = 0; j < 

求两个数的最大公约数和最小公倍数 C语言

C程序设计第八章的第一道题目,求两个数的最大公约数和最小公倍数.需要注意一下几点: 1.最大公约数和最小公倍数间的关系: 设两个数是a,b最大公约数是p,最小公倍数是q 那么有这样的关系:ab=pq 所以q=ab/p.2.任意整数和0的公约数是该整数的所有约数,所以它们的最大公约数为该整数本身.3.碾转相除法:被除数%除数=余数,如果余数不为0,就让原来的除数做为被除数,余数作为除数,再进行运算 被除数%除数=余数,直到得到的余数为0为止,此时的除数就是最大公约数. #include <stdi

c语言:求两个数的最大公约数。

求两个数的最大公约数. 程序: #include <stdio.h> int main() { int num1, num2, t; printf("请输入两个正整数:"); scanf("%d%d",&num1, &num2);//7,8 while (t = num1%num2)//7           1        0,循环结束 { num1 = num2;     //8           7 num2 = t;     

【c语言】求两个数中不同的位的个数

// 求两个数中不同的位的个数 #include <stdio.h> int dcount(int a,int b) { int count = 0; int num = a ^ b; while (num) { count++; num = num & (num - 1); } return count; } int main() { printf("%d\n", dcount(3, 5)); return 0; } 版权声明:本文为博主原创文章,未经博主允许不得

编写C语言程序求两个数的最大公约数

//求两个数的最大公约数 #include <stdio.h> int main() {  int num1,num2;  int temp;  scanf("%d%d",&num1,&num2);  //核心算法  while(num1 % num2 != 0)  {   temp = num2;   num2 = num1%num2;   num1 = temp;  }  printf("最大公约数为:%d\n",num2);  re

写一个方法,求两个数的最大公约数和最小公倍数。

package homework0702; /* * 最大公约数 利用辗转相除法求解两个正整数的最大公约数 在循环中,只要除数不等于0,用较大的数除以较小的数,将小的一个数作为下一轮循环的大数,取得的余数作为下一轮循环较小的数,如此循环直到较小的数值为0,返回较大的数.即为最大公约数. 辗转相除法(欧几里得算法) 定理:两个整数的最大公约数等于其中较小的那个数和两数的相除余数的最大公约数.最大公约数(greatest common divisor)缩写为gcd. 最小公倍数 最小公倍数 = (a

求两个数的最大公约数

求两个数的最大公约数 问题:给定两个正整数a和b,求他们的最大公约数. 最简单的方法就是穷举法,如果a>b,那么依次计算1~b的所有整数是否是a和b的公约数. public static void main(String[] args) { long timer = System.currentTimeMillis(); System.out.println(getGCB(1000234234,1242342390)); System.out.println(System.currentTime

求两个数的最大公约数和最小公倍数

import java.util.Scanner; //求两个数的最大公约数,最小共倍数. public class CommonMaxDivisor { public static void main(String[] args){ Scanner scanner=new Scanner(System.in); int m=scanner.nextInt(); int n=scanner.nextInt(); scanner.close(); CommonMaxDivisor cmd=new

编程题:返回指针值的函数,求两个数中较大的数。

#include<stdio.h> int *max(int *x,int *y) { int *q; if(*x>*y)  q=x; else  q=y; return q; } void main() { int a,b,*p; scanf("%d,%d",&a,&b); p=max(&a,&b); printf("%d,%d,max is %d\n",a,b,*p); } 编程题:返回指针值的函数,求两个数中较