求最大公约数、最小公倍数

最大公倍数
若 a、b 全为零则它们的最大公约数不存在;若 a、b 其中之一为零,则它们
的最大公约数为 a、b 中非零的那个;若 a、b 都不为零,则使新 a = b;新 b = a % b 然后重复该过程。
最小公约数
a、b 两数的最小公倍数为两数的乘积除以它们的最大公约数。
题目描述:
输入两个正整数,求其最大公约数。
输入:
测试数据有多组,每组输入两个正整数。
输出:
对于每组输入 ,请输出其最大公约数。
样例输入:
49 14
样例输出:

#include <stdio.h> 
int gcd(int a,int b) { 
if (b == 0) return a; //若b为零则最大公约数为 a 
else return gcd(b,a % b); //否则 ,则改为求 b与a%b 的最大公约数
} 
int main () { 
int a , b; 
while (scanf ("%d%d" ,& a,& b) != EOF ) { //输入两个正整数
printf( "%d\n" ,gcd(a,b)); //输出所求的最大公约数
} 
return 0; 
} 
该代码把求最大公约数的欧几里得算法写成了递归的形式,若读者对理解递归有困难,
这里我们也给出其非递归形式,供读者参考。
代码 3.6 
#include <stdio.h> 
int gcd(int a,int b) { 
while(b != 0) { //只要 b不为 0则一直持续该过程
int t = a % b; 
a = b; //使a变成 b 
b = t; //使b变成 a % b 
} 
return a; //当b为0时,a即是所求
} 
int main () { 
int a , b; 
while (scanf ("%d%d" ,& a,& b) != EOF ) {
printf( "%d\n" ,gcd(a,b)); 
} 
return 0; 
}
全部评论

相关推荐

鼠鼠第一次实习,啥也不懂一直是自己一个人吃的饭,不会做工作老是被嫌弃,大人的世界是这样的吗?
我是星星我会发亮:好的mt有两种,一种愿意教你的,一种几乎什么活都不给你派让你很闲允许你做自己事情的
点赞 评论 收藏
分享
05-20 13:59
门头沟学院 Java
米黑子米黑子:你这个成绩不争取下保研?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务