最大公约数和最小公倍数算法
编辑:谯胜平 分类:程序与算法 标签:最大公约数,最小公倍数 发布时间:2019-05-11 浏览次数:885次
一、分析
设a,b均为正整数。
最大公约数
gcd(a, b)表示求最大公约数。使用欧几里得算法(即辗转相除法),其基本公式如下:
递归式:gcd(a, b) = gcd(b, a % b);
递归边界:gcd(a, 0) = a;
最小公倍数
lcm(a, b)表示求最小公倍数。通过最大公约数可以很快求出最小公倍数,其公式如下:
lcm(a, b) = a * b / gcd(a, b) = a / gcd(a, b) * b(防止a*b溢出);
二、代码
最大公约数:
#include<stdio.h> #include<algorithm> //最大公约数 int gcd(int a, int b){ if(b == 0) return a; else return gcd(b, a % b); } int main() { int a, b; while(scanf("%d %d", &a, &b)!= EOF){ printf("%d\n", gcd(a, b)); } return 0; }
最小公倍数:
#include<stdio.h> #include<algorithm> //最大公约数 int gcd(int a, int b){ if(b == 0) return a; else return gcd(b, a % b); } //最小公倍数 int lcm(int a, int b){ return a / gcd(a, b) * b; } int main() { int a, b; while(scanf("%d %d", &a, &b)!= EOF){ printf("%d\n", lcm(a, b)); } return 0; }
热门文章
猜你喜欢
文章标签
- 考研经验(10)
- 计算机考研(8)
- 408(1)
- 数学一(1)
- codeup(4)
- 字符串处理(5)
- web(3)
- 学科评估(2)
- scanf(2)
- gets(1)
- getchar(1)
- sublime text(2)
- java(1)
- 五子棋(1)
- printf(1)
- 最大公约数(1)
- 最小公倍数(1)
- mysql(1)
- 作息时间(2)
- STL(1)
- PAT(2)
- 富文本编辑器(1)
- 数据类型(1)
- 完全二叉树(1)
- 闰月(1)
- 晴天的魔法乐园(6)
- 递归(1)
- 棋盘覆盖问题(1)
- PPT模板(1)
- 谷歌(1)
- unzip(1)
- gcc(1)
- ubuntu(1)
- getline()(1)
- 日历(1)
- 作息时间表(1)
友情链接