求“最小公倍数”的算法代码,不理解这段代码的思路

问题描述:编写一函数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对不上

辗转相除法,一个求大公约数的方法,证明方法可以看看度娘,一时半会不好说。


11行的if可以保证a>b
下面的while循环就是辗转相除法,循环结束之后a就是最大公约数。
lcm的作用就是求最小公倍数,这个直接举例来说。比如15和21的最小公倍数,最大公约数为3,最小公倍数就是15x21/3=105。
原理就是105=3x7x5,15=5x3,21=3x7,公约数为3(所以约去一个3就是最小倍数)。s=s/a=21x15/3=3x5x3x7=3x5x7。

辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。

  例如,求(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。

  用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。最后所得的那个最大公约数,就是所有这些数的最大公约数