代码编织梦想

按如下函数原型,采用穷举法编写计算最大公约数的函数Gcd(),在主函数中调用该函数计算并输出从键盘任意输入的两整数的最大公约数。穷举法的基本思想是:先找到a和b中的较小者t,然后从t开始逐次减1尝试每种可能,即检验t到1之间的所有整数,第一个满足公约数条件的t,就是a和b的最大公约数。
/* 函数功能:计算a和b的最大公约数,输入负数时返回-1 */
int Gcd(int a, int b)
要求如下:
(1)从键盘任意输入的两整数
     主函数调用Gcd()函数,并输出两整数的最大公约数。
(2)Gcd函数原型为:
     int Gcd(int a, int b);
     如果输入的数不是正整数,则返回-1,否则,返回两个数的最大公约数。
(3)**输入提示信息格式要求:"Input a,b:"
       输入格式:"%d,%d"
     **输出提示信息要求:
     如果输入的数不是正整数,则输出"Input number should be positive!\n",否则按如下格式输出"Greatest Common Divisor of %d and %d is %d\n"
#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
int Gcd(int a, int b);
int main()
{
	int a, b;
	int m;
	printf("Input a,b:");
	scanf("%d,%d", &a, &b);
	if (a <= 0 || b <= 0)
	{
		printf("Input number should be positive!\n");
	}
	else
	{
		 m = Gcd(a, b);
		 printf("Greatest Common Divisor of %d and %d is %d\n", a, b, m);
	}
	
}

int Gcd(int a, int b)
{
	int t;
	if (a < b)
	{
		t = a;
	}
	else
	{
		t = b;
	}
	for (int i = t; t > 0; t--)
	{
		if (a % t == 0 && b % t == 0)
		{
			break;
		}
	}
	int k = t;
	return k;

}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_74343239/article/details/128859241

穷举法求n个数的最大公约数和最小公倍数-爱代码爱编程

第二章作业 一、题目 基本要求: 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。 提高要求: 思考一个“求公约数”和“求公倍数”之类问题的“逆问题”,这个问题是这样的:已知正整数a0,a1,b0,b1,设某未知正整数x满足: 1、  x和a0的最大公约数是a1; 2、  x和b0的最小公倍数是b1。

穷举法求最大公约数 C语言-爱代码爱编程

穷举法求最大公约数 问题描述 尝试基于以下逻辑编程计算最大公约数:由于a和b的最大公约数不可能比a和b中的较小者还大,否则一定不能整除它,因此,先找到a和b中的较小者t,然后从t开始逐次减1尝试每种可能,即检验ttt到1之间的所有整数,第一个满足公约条件的t,就是a和b的最大公约数。 输入 输入为两个正整数 输出 输出为两个正整数的最大公约数

python求两个数的最大公约数穷举法_最大公约数GCD算法-爱代码爱编程

采用Python实现四种最大公约数(greatest common divisor)算法,并比较评估性能。 算法原理: 1、辗转相除法: 已知a,b,c为正整数,若a除以b余c,则GCD(a,b)=GCD (b,c)。 2、更相减损术: 任意给定两个正整数,若是偶数,则用2约简。 以较大的数减较小的数,接着把所得的差与较小的数

求最大公约数之:穷举法求两个数的最大公约数-爱代码爱编程

穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤: 从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数 。 定义:对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数 i 能同时被a和b所整除,则 i 即为最大公约数。 ① i= a,b中的小数 ② 若a,b能同时被i整除,则i即为最大公约

python求两个数的最大公约数穷举法_五十九、如何求N个数的最大公约数和最小公倍数...-爱代码爱编程

「@Author:Runsen」 ❝ 编程的本质来源于算法,而算法的本质来源于数学,编程只不过将数学题进行代码化。「---- Runsen」 ❞ 上次介绍了短除法的因式分解,下面正式进入求解:「两个及以上个数的最大公约数与最小公倍数」 基本要求:求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决

求最大公约数穷举法c语言,c语言求两个数的最大公因数(穷举法,欧几里得算法,递归)...-爱代码爱编程

/*主函数Gcd为求公因数的函数输入为负时返回-1*/ int main() { int a, b; printf("Input a,b:"); scanf("%d,%d",&a,&b); if (a < 0 || b < 0) printf("Input number should be positive!\

c语言编程最大公约数穷举发,C语言基本算法 :1.求最大公约数与最小公倍数-爱代码爱编程

C语言基本算法 :1.求最大公约数与最小公倍数 一.最大公约数: 最大公约数目前有三种求法:更相减损术、辗转相除法以及穷举法。 1.更相减损术: 算法介绍:设两个整数数a和b,以较大数减较小数,得出的差与减数比较大小,再次使用较大数减较小数,直到减数与差相等,此时减数(差)即为最大公约数。 代码展示: #include #include

C语言求最大公约数和最小公倍数(穷举法)-爱代码爱编程

最大公约数:可以同时被两个数整除的最大的那个数就是最大公约数,比如说6和12,那么6可以同时被两个数整除,最大公约数不会超过两个整数中较小的一个。 最小公倍数:最小公倍数两个或多个整数公有的倍数叫做它们的公倍数,其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。 例如:【3和4】3的倍数有6、9、12、15、18、21、24……;4的倍数有4、8、

求最大公约数的4种方法C语言(辗转相除法、辗转相减法、穷举法、递归法)-爱代码爱编程

最大公约数,也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个。 目录 问题描述 辗转相除法(欧几里得算法) 代码实现  辗转相减法 代码实现 暴力穷举法 代码实现 递归法 代码实现 测试及结果 问题描述 随机输入两个数,求其最大公约数 辗转相除法(欧几里得算法) 辗转相除法依赖于一个定

problem d. s07-07-1 穷举法求最大公约数_131452lin的博客-爱代码爱编程

尝试基于以下逻辑编程计算最大公约数:    由于a和b的最大公约数不可能比a和b中的较小者还大,否则一定不能整除它,因此,先找到a和b中的较小者t,然后从t开始逐次减1尝试每种可能,即检验t到1之间的所有整数,第一个满足公约条件的t,就是a和b的最大公约数。 输入 输入为两个正整数 输出 输出为两个正整数的最大公约数 样例 标准输入 6 9 标

【c语言】用三种不同的方法求两个正整数的最大公约数_钰爱&的博客-爱代码爱编程

【穷举法】 由于a和b的最大公约数不可能比a和b中的较小者还大,否则一定不能整除它,因此,先找a和b中的较小者t,然后从t开始逐渐减1尝试每种可能,及检测t到1之间的所有整数,第一个满足公约数条件的t,就是a和b的最大公约数 #include<stdio.h> int GCD(int a,int b) { int c,i; if(a&l