题目：随机输入两个数，求其最大公约数
在此展示三种常用解题思路
1.首先展示第一种思路
#include <stdio.h> int main(){int a,b,c; //先定义变量printf("请输入：n");scanf("%d%d",&a,&b); //输入两个整型数字if(a<b) {c=a;a=b;b=c; //保证a≥b}int i = 0;for(i = b;i>0;i--){if(a%i == 0 && b%i == 0) {printf("gcd(%d,%d) = %dn",a,b,i);break;}}return 0;}
2.辗转相除法
这里涉及到一个公式：GCD(a,b) = GCD(b,a%b)
#include <stdio.h>int main(){int a,b,c;printf("请输入：");scanf("%d%d",&a,&b);if(a<b){c = a;a = b;b = c; //确保a≥b}while(b != 0) {c = b;b = a%b; //辗转相除：相比第一种思路大大提高了代码的效率a = c;}printf("最大公约数为：%d",a);return 0;}
还有一种运用递归的思想
#include <stdio.h>void Gcd(int a,int b){if(a > b){if(a % b == 0){return b;}else{return Gcd(b,a%b); }}else{if(b % a == 0){return a;}else{return Gcd(a,b%a);}}}int main(){int a, b;int c = 0;printf("请输入两个整数：");scanf("%d%d",&a, &b);c = Gcd(a, b);printf("GCD（%d,%d）=%dn",a,b,c);}
3.更相减损术
定义：(如果需要对分数进行约分，那么)可以折半的话，就折半(也就是用2来约分)。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。
#include <stdio.h>main(){int a,b;printf("请输入两个正整数：");scanf("%d%d",&a,&b);while(a%2==0){a/=2;}while(b%2==0){b/=2;} //让两个数都为奇数while(a!=b){if(a>b) a=a-b; else b=b-a; //更相减损术：当差值等于减数的值时即为最大公约数}printf("GCD=%dn",a);return 0;}
本文结束，感谢阅览！