求最大公因数
最大公因数：也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。
一、穷举法
思路：找到两个数之间的最少值 使用第三接收最小值，然后通过判断两者%n是否同时等于0，同时为0证明就是两者的最大公因数，不是就n–继续判断。
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h>c int 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; }
