1、求两个数的最大公约数
1.1 普通实现方法
#include<stdio.h> int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b); int m = 0; //找出最小值 m = (a > b ? b : a); //假设m为最大公约数 while (1) { if (a % m == 0 && b % m == 0) { break; } m--; } printf("%d\n", m); return 0; }
1.2 优化后的方法 “辗转相除法”
#include<stdio.h> int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b); int m = 0; while (m=a % b) { a = b; b = m; } printf("%d\n", b); return 0; }
2、求两个数的最小公倍数
2.1 普通实现方法
#include<stdio.h> int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b); int m = 0; m = (a > b ? a : b); while (1) { if (m % a == 0 && m % b == 0) { break; } m++; } printf("%d\n", m); return 0; }
2.2 优化后的方法
假如m为a和b的最大公约数，则a和b的最小公倍数为 a*b/m
#include<stdio.h> int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b); int m = 0; int n = 0; n = a * b; while (m = a % b) { a = b; b = m; } printf("%d\n", n/b);
