给定两个数，求这两个数的最大公约数
1:
思路：
24 18 - 最大公约数不会超过18
24 17
24 16
… …
24 6
让较小的数字往下找，直到能同时被24和18整除
#include<stdio.h> #pragma warning(disable:4996) int main() { int m = 0; int n = 0; scanf("%d%d", &m,&n); //假设m和n的最大公因数是较小值,将较小值放到gcd里 int gcd = 0; if (m > n) gcd = n; else max = m; while(1) { if(m % gcd == 0 && n % gcd == 0) { printf("最大的公约数是:%d\n", gcd); break; } max--; } }
2:
欧几里得算法 - 俗称辗转相除法
24 18
24 % 18 = 1 … 6
18 % 6 = 3 … 0
以除数和余数循环做除法运算，当余数为0时，取当前算式除数为最大公约数
这里6就是24和18的最大公约数
#include<stdio.h> #pragma warning(disable:4996) int main() { int m = 0; int n = 0; scanf("%d%d", &m, &n); //保证最大值在永远是除数 if (m < n) { int temp = m; m = n; n = temp; } while (m % n) { if( m % n != 0 )//更换除数和被除数 { int ret = m % n; m = n; n = ret; } else { printf("最大公约数是%d\n", n); break; } } return 0; }
优化2：
其实在最开始没必要把最大值设置为除数
18 % 24 = 0 … 18 ->交换后24 % 18
#include<stdio.h> #pragma warning(disable:4996) int main() { int m = 0; int n = 0; int ret = 0; scanf("%d%d", &m,&n); while (ret = m % n) { m = n; n = ret; } printf("最大的余数是%d\n", n); return 0; }
