最大公约数与最小公倍数最大公约数与最小公倍数

1. 最小公倍数 a,b的最小公倍数等于 a*b/最大公约数
2. 最大公约数 2.1 辗转相除法
① a%b得到余数c
② 若c=0，则c即是最大公约数
③ 若c≠0，则 a=b,b=c，再返回①
注意：这里假设a,b都是正数，因此无需判断a,b的大小，因为当a

#include using namespace std; int main() { int a=0,b=0,c=0; while(scanf("%d %d",&a,&b)) { int m=a,n=b; while(n!=0) { c=m%n; m=n; n=c; } printf("The Greatest common divisor between %d and %d is:%d\n",a,b,m); printf("The least common multiple between %d and %d is:%d\n",a,b,a*b/m); } }

2.2 更相减损法
① 若a>b,则a=a-b;
② 若a ③ 若a=b,则a or b就是最大公约数

#include using namespace std; int main() { int a=0,b=0; while(scanf("%d %d",&a,&b)) { int m=a,n=b; while(m!=n) { if(m>n) m=m-n; else n=n-m; } printf("The Greatest common divisor between %d and %d is:%d\n",a,b,m); printf("The least common multiple between %d and %d is:%d\n",a,b,a*b/m); } }

【最大公约数与最小公倍数】以上