问题描述:编写一函数lcm,求两个正整数的最小公倍数。
#include <stdio.h>
void lcm(int* s, int* b)
{
*s = *s / *b;
}
main(void)
{
int a, b, t, s;
scanf("%d%d", &a, &b);
s = a * b;
if (a < b)
{
t = a; a = b; b = t;
}
while (b)
{
t = a % b;
a = b;
b = t;
}
lcm(&s, &a);
printf("%d", s);
return 0;
}
int* s是什么呀?为什么要s = *s / *b;啊?下面为什么又要inta,b,t,s;啊?总之全部都看不明白!希望大家帮我解析一下整个代码。非常感谢大家!
while循环辗转相除法得到a为最大公约数。lcm是求最小公倍数。最小公倍数=两数乘积除以最小公约数。由于s是a * b,即两数乘积,a是最大公约数,lcm函数用指针作为参数,所以需要 * s, * a获得对应的值进行相除。得到的结果记录到s返回,再printf输出
就是感觉lcm(&s, &a)中的&a和void lcm(int* s, int* b)中的int* b对不上
辗转相除法,一个求大公约数的方法,证明方法可以看看度娘,一时半会不好说。
辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。
例如,求(319,377):
∵ 319÷377=0(余319)
∴(319,377)=(377,319);
∵ 377÷319=1(余58)
∴(377,319)=(319,58);
∵ 319÷58=5(余29)
∴ (319,58)=(58,29);
∵ 58÷29=2(余0)
∴ (58,29)= 29;
∴ (319,377)=29。
用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。最后所得的那个最大公约数,就是所有这些数的最大公约数