最大公约数与最小公倍数常用于分数的运算
这里是从浙江大学C语言慕课翁恺大大那学得辗转相除法
1 #include <stdio.h> 2 #include <stdlib.h> 3 /*辗转相除法 4 1、如果b=0,计算结束，a就是最大公约数 5 2、否则，计算a除于b的余数，让a=b,b等于那个余数，回到第一步 6 */ 7 int main() 8 { 9 int a ,b ,t; 10 scanf("%d %d",&a,&b); 11 int m=a; 12 int n=b; 13 while (b != 0 ){ 14 t = a % b; 15 a = b; 16 b = t; 17 } 18 printf("最大公约数是%d",a); 19 printf("最小公倍数是%d",m*n/a); 20 return 0; 21 }
可手动执行一遍 设 a=12 b=15
a b t
12 15 12
15 12 3
12 3 0
3 0
此时b=0 , 可得最大公约数是3，最小公倍数是12*15/3=60
然后来一个简单应用
7-33 有理数加法（15 分）
本题要求编写程序，计算两个有理数的和。
输入格式：
输入在一行中按照a1/b1 a2/b2的格式给出两个分数形式的有理数，其中分子和分母全是整形范围内的正整数。
输出格式：
在一行中按照a/b的格式输出两个有理数的和。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。
输入样例1：
1/3 1/6
输出样例1：
1/2
输入样例2：
4/3 2/3
输出样例2：
2
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<math.h> 4 #include <string.h> 5 6 7 int main () 8 { 9 int a,b,c,d; 10 char s1,s2; 11 int t; 12 scanf("%d%c%d %d%c%d",&a,&s1,&b,&c,&s2,&d); 13 //求b和d之间的最小公倍数 14 int m=b,n=d; 15 int sum1,g1; //分子，分母 16 while( n!=0 ){ 17 t = m%n; 18 m = n; 19 n = t; 20 } 21 g1 = b*d/m; 22 sum1 = a*g1/b+c*g1/d; 23 24 //求sum1和g1之间的最大公约数 25 int g = g1; 26 int sum =sum1; 27 while ( g1!=0 ){ 28 t = sum1%g1; 29 sum1 = g1; 30 g1 = t; 31 } 32 g /= sum1; 33 sum /= sum1; 34 if( g==1 ){ 35 printf("%d",sum); 36 } 37 else{ 38 printf("%d%c%d",sum,s1,g); 39 } 40 41 return 0; 42 }