[考研]东大C语言编程题——02最大公约数和最小公倍数
2017-07-19 本文已影响54人
LINCHUAN114
title: '[考研]东大C语言编程题——02最大公约数和最小公倍数'
date: 2017-09-08 22:30:48
tags: [考研,东北大学,C]
thumbnail: https://img.haomeiwen.com/i3635391/6ba8d3822c99643d.jpg
toc: true
题目标记：无
题目描述
输入m、n，求其最大公约数和最小公倍数。
解题思路
最常见的是碾转相除法，利用大数除以小数得到余数，当余数为零时，则被除数则为最大公约数。两数乘积除以最大公约数即为最小公倍数。形象的说法如下：
设两整数a,b：
① a%b=c；
② 判断c==0?b为最大公约数:{a=b;b=c;}
以上两步循环，最终得到最大公约数m
其最小公倍数：a*b/m
代码
#include <stdio.h>
int main(){
int m,n,p,temp;
scanf("%d%d",&m,&n);
p=m*n;
if(m<n){ //保证大数在前，小数在后
temp=m;
m=n;
n=temp;
}
while(m%n!=0){ //辗转相除法
temp=m%n;
m=n;
n=temp;
}
printf("最大公约数:%d，最小公倍数：%d\n",n,p/n);
return 0;
}
运行结果
运行结果
