网站建设网络,php网站如何做特效,goland 网站开发,没有广告的免费个人网站建设求最大公因数
最大公因数#xff1a;也称最大公约数、最大公因子#xff0c;指两个或多个整数共有约数中最大的一个。
一、穷举法
思路#xff1a;找到两个数之间的最少值 使用第三接收最小值#xff0c;然后通过判断两者%n是否同时等于0#xff0c;同时为0证明就是两者…求最大公因数
最大公因数也称最大公约数、最大公因子指两个或多个整数共有约数中最大的一个。
一、穷举法
思路找到两个数之间的最少值 使用第三接收最小值然后通过判断两者%n是否同时等于0同时为0证明就是两者的最大公因数不是就n–继续判断。
#define _CRT_SECURE_NO_WARNINGS
#include stdio.hcint main()
{//穷举法int a 0;int b 0;scanf(%d %d,a,b);int n a b ? b : a;//获取最小值while (a % n ! 0 || b % n ! 0)//作为判断条件{n--;}printf(%d,n);return 0;
}二、辗转相除法
思路两个数通过反复求模 获取到一个值当两个数取模时值为0时证明该被取模的数就是两数的最大公因数。
例如 a 24 b 16 a % b 8 此时a 8,b 16, 再次循环 b % a 0 ,那么就证明a为最大公因数。需要注意的是 必须是大的数取余小的数 就需要进行判断。
总代码
#define _CRT_SECURE_NO_WARNINGS
#include stdio.hint main()
{int a 0;int b 0;scanf(%d %d,a,b);while (a b){if (a b){a % b;}else{b % a;}}printf(%d,a b ? a : b);return 0;
}三、更相相损法
思路两数通过不断相损(相减)当两者相等时就是最大公因数。
例如 a 24 b 16,通过条件判断使 a - b,那么此时a 8 ,b 16,再次进行条件判断 从而使 a b获得最大公因数。
总代码
#define _CRT_SECURE_NO_WARNINGS
#include stdio.hint main()
{int a 0;int b 0;scanf(%d %d,a,b);while (a ! b){if (a b){a - b;}else{b - a;}}printf(%d,a);return 0;
}
