本文主要是介绍C语言第二十弹--求最大公因数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
求最大公因数
最大公因数:也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。
一、穷举法
思路:找到两个数之间的最少值 使用第三接收最小值,然后通过判断两者%n是否同时等于0,同时为0证明就是两者的最大公因数,不是就n–继续判断。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>cint 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.h>int 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.h>int 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;
}
这篇关于C语言第二十弹--求最大公因数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!