C语言 如何求两整数的最大公约数与最小公倍数

目录
  • 题目
  • 思路
  • 代码
    • 法一
    • 法二（局部变量）
    • 法三（全局变量）
  • 运行结果

题目

用一函数求最大公约数，用另一函数调用此函数求出最大公约数，并用求出的最大公约数求最小公倍数。

具体要求如下：

  • ①用全局变量。将最大公约数与最小公倍数设为全局变量，在主函数中输出它们的值。
  • ②不用全局变量。最大公约数和最小公倍数由被调模块返回值。

思路

从两个数中选一个数，从这个数开始，逐步减一，当能够同时被两个数整除时，结束循环，即为最大公约数。

最小公倍数*最大公约数=两个数乘积。

代码

法一

#include<stdio.h>
int main()
{
	int x,y,z,a,b,c,d,t,x_0,y_0;
	printf("请输入两个整数：");
	scanf("%d,%d",&x,&y);
	x_0=x;y_0=y;
	if(x<y) t=x,x=y,y=t;
	do
	{
		a=x%y;
		if(a!=0) x=y,y=a,a=x%y;
	}while(x%y!=0);
	printf("这两个整数的最大公约数为：%d\n",y);
	c=x_0/y;d=y_0/y;
	z=y*c*d;
	printf("这两个整数的最小公倍数为：%d\n",z);
	return 0;
}

法二（局部变量）

#include<stdio.h>
int yue(int a,int b)
{
	int i,s,max_yue;
	for(i=a;i>0;i--)
		if(a%i==0&&b%i==0) {max_yue=i;break;}
	return(max_yue);
}
int bei(int a,int b)
{
	int yue(int a,int b);
	int max_bei;
	max_bei=a*b/yue(a,b);
	return(max_bei);
}
int main()
{
	int a,b,t,max_yue,max_bei;
	int yue(int a,int b);
	int bei(int a,int b);
	printf("请输入两个正整数：");
	scanf("%d,%d",&a,&b);
	if(a<b) {t=a;a=b;b=t;}
	max_yue=yue(a,b);
	max_bei=bei(a,b);
	printf("这两个数最大公约数为：%d\n最小公倍数为：%d\n",max_yue,max_bei);
}

法三（全局变量）

#include<stdio.h>
int max_yue,max_bei;
int yue(int a,int b)
{
	int i;
	for(i=a;i>0;i--)
		if(a%i==0&&b%i==0) {max_yue=i;break;}
	return(max_yue);
}
int bei(int a,int b)
{
	int yue(int a,int b);
	max_bei=a*b/yue(a,b);
	return(max_bei);
}
int main()
{
	int a,b,t;
	int yue(int a,int b);
	int bei(int a,int b);
	printf("请输入两个正整数：");
	scanf("%d,%d",&a,&b);
	if(a<b) {t=a;a=b;b=t;}
	max_yue=yue(a,b);
	max_bei=bei(a,b);
	printf("这两个数最大公约数为：%d\n最小公倍数为：%d\n",max_yue,max_bei);
}

运行结果

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 详解C语言求两个数的最大公约数及最小公倍数的方法

    求两个正整数的最大公约数  思路:这是一个很基本的问题,最常见的就是两种方法,辗转相除法和辗转相减法.通式分别为 f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0).根据通式写出算法不难,这里就不给出了.这里给出<编程之美>上的算法,主要是为了减少迭代的次数.      对于x和y,如果y = k * y1, x= k * x1,那么f(x, y) = k * f(x1, y1).另外,如果x = p * x1,假设p为素数

  • C语言实现求最大公约数的三种方法

    C语言实现求最大公约数的三种方法

    目录 题目描述 问题分析 代码实现 方法一:穷举法 方法二:辗转相除法 方法三:更相减损法 题目描述 求任意两个正整数的最大公约数 问题分析 最大公因数,也称最大公约数.最大公因子,指两个或多个整数共有约数中最大的一个.a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号.求最大公约数有多种方法,常见的有质因数分解法.短除法.辗转相除法.更相减损法.与最大公约数相对应的概念是最小公倍数,a,b的最小公倍数记为[a,b]. --百度

  • C++ 实现求最大公约数和最小公倍数

    C++ 实现求最大公约数和最小公倍数 最大公约数 辗转相除法: int maxDivisor(int a, int b) { int c = b; while (a%b != 0) { c = a%b; a = b; b = c; } return c; } 辗转相减法: int maxDivisor(int a, int b) { while (a != b) { if (a>b) a = a - b; else b = b - a; } return a; } 感谢阅读,希望能帮助到大家,谢

  • C语言 如何求两整数的最大公约数与最小公倍数

    目录 题目 思路 代码 法一 法二(局部变量) 法三(全局变量) 运行结果 题目 用一函数求最大公约数,用另一函数调用此函数求出最大公约数,并用求出的最大公约数求最小公倍数. 具体要求如下: ①用全局变量.将最大公约数与最小公倍数设为全局变量,在主函数中输出它们的值. ②不用全局变量.最大公约数和最小公倍数由被调模块返回值. 思路 从两个数中选一个数,从这个数开始,逐步减一,当能够同时被两个数整除时,结束循环,即为最大公约数. 最小公倍数*最大公约数=两个数乘积. 代码 法一 #include<

  • C语言辗转相除法求2个数的最小公约数

    辗转相除法最大的用途就是用来求两个数的最大公约数. 用(a,b)来表示a和b的最大公约数. 有定理: 已知a,b,c为正整数,若a除以b余c,则(a,b)=(b,c). (证明过程请参考其它资料) 例:求 15750 与27216的最大公约数. 解: ∵27216=15750×1+11466 ∴(15750,27216)=(15750,11466) ∵15750=11466×1+4284  ∴(15750,11466)=(11466,4284) ∵11466=4284×2+2898  ∴(114

  • C#获取两个数的最大公约数和最小公倍数示例

    最大公约数:指两个或多个整数共有约束中最大的一个. 最小公倍数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个. 复制代码 代码如下: /// <summary>/// 最大公约数/// </summary>/// <param name="a"></param>/// <param name="b"></param>/// &

  • Python自定义函数实现求两个数最大公约数、最小公倍数示例

    Python自定义函数实现求两个数最大公约数、最小公倍数示例

    本文实例讲述了Python自定义函数实现求两个数最大公约数.最小公倍数.分享给大家供大家参考,具体如下: 1. 求最小公倍数的算法: 最小公倍数  =  两个整数的乘积 /  最大公约数 所以我们首先要求出两个整数的最大公约数, 求两个数的最大公约数思路如下: 2. 求最大公约数算法: ① 整数A对整数B进行取整, 余数用整数C来表示    举例: C = A % B ② 如果C等于0,则C就是整数A和整数B的最大公约数 ③ 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 1, 2

  • python如何求解两数的最大公约数

    题目: 给定两个自然数,求这两个数的最大公约数. 分析: 单看题目的话,非常简单,我们可以循环遍历自然数,如果能够整除两个自然数,就把这个数记下来,在这些记录中找到最大的一个. 但是这样做有几个缺点:一是做除法计算量比较大,二是遍历所有自然数完全没有必要.另外,如果能够循环,还是不要递归,因为Python的函数递归最大栈空间是1000(如果我没有记错的话),如果数字大一些,很容易出现爆栈. 所以在这里有两种处理方法: 1.如果较大的自然数除较小的一个自然数,取得余数,较小的自然数和余数的最大公约

  • python求最大公约数和最小公倍数的简单方法

    python怎么求最大公约数和最小公倍数 一.求最大公约数 用辗转相除法求最大公约数的算法如下: 两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数.比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数. 具体代码如下: def gongyue(a, b): """ 欧几里得算法----辗转相除法 :param a: 第一个数 :param b: 第二个数 :return: 最大公约数 "

  • C语言求两个正整数的最大公约数示例代码

    目录 前言 1.穷举法 2.欧几里得算法(辗转相除法) 3.递归方法 附:相减法 总结 前言 两个正整数的最大公约数(Greatest Common Divisor, GCD)是能够整除这两个整数的最大整数.两个正整数的最大公约数的求法有多种解答,本文就三种方法做详细介绍:穷举法.欧几里得算法(辗转相除法).递归方法. 我们从一道问题来引入:编写计算最大公约数的函数Gcd(),在主函数中调用该函数计算并输出从键盘任意输入的最大公约数. 1.穷举法 根据最大公约数的定义,我们可以采用一种最简单的方

  • C语言求两个字符串的最长公共子串

    本文实例讲述了C语言求两个字符串的最长公共子串的方法.分享给大家供大家参考.具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * str3); int stringLength(char * str); void main(){ char str1[50]; char st

随机推荐