[萌新计算] 公约数&公倍数

请注意,本文编写于 141 天前,最后修改于 23 天前,其中某些信息可能已经过时。

C 语言上机实验课题目要求编程计算正整数的最大公约数、最小公倍数、质因数分解。算法没什么思路,不知道从哪里下手(很多问题也是这样,不知道用计算机的加减乘除怎么解决),所以搜了搜参考资料,在 CSDN 看到一篇文章《【C语言】4种方法求最大公约数和最小公倍数》,觉得写的很好,简单记录一下。

由于最小公倍数可以用下面的方法计算,所以下面主要讨论最大公约数的计算思路。(我居然今天才想起来知道最小公倍数能这么简单的算出来)

最小公倍数 = 数 a × 数 b ÷ 最大公约数

 

穷举法

穷举法(也叫枚举法)的基本思想是根据题目的部分条件确定答案的大致范围,并在此范围内对所有可能的情况逐一验证,直到全部情况验证完毕一个一个列。上代码就是一把梭!求数就是挨个列!基本思路是:从两个数中较小数开始由大到小列举约数,直到找到公约数时中断列举,得到的公约数便是最大公约数。

解题步骤:

  • 求最大公约数
    对两个正整数 a,b,如果在区间 [a,0] 或 [b,0] 内能找到一个整数 temp 能同时被 a 和 b 整除,则 temp 为 a,b 的最大公约数。
  • 最小公倍数
    对两个正整数 a,b,如果若干个 a 之和(或 b 之和)能被 b 所整除(或能被 a 所整除),则这个和数为 a,b 的最小公倍数。

有了这个思路,看了下原来的代码,理解消化一下动手改成老师最爱的 C 语言作业格式:

#include <stdio.h>
 
int main()
{
    int a,b,m,n;
    scanf("%d%d",&a,&b);
    m=gcd(a,b);
    n=lcm(a,b);
    printf("%d与%d的最大公约数是%d\n",a,b,m);
    printf("%d与%d的最小公倍数是%d\n",a,b,n);
}
int gcd(int a,int b)    
{
    int temp;
    temp=(a>b)?b:a;   // 取出 a,b 两数中的最小值
    while(temp>0)
    {
        if (a%temp==0&&b%temp==0)    // 找到一个数同时被 a,b 整除时跳出循环
            break;
        temp--;                      // 未找到该数则变量自减直到能被 a,b 同时整除
    }
     
    return temp;
}
int lcm(int a,int b)
{
    int p,q,temp;
    p=(a>b)?a:b;      // 求两个数中的最大值
    q=(a>b)?b:a;      // 求两个数中的最小值
    temp=p;           // 最大值赋给 p 用于变量自增
    while(1)          // 保持循环直至找到最小公倍数
    {
        if(p%q==0)
            break;    // 只要找到变量的和数能被 a 或 b 所整除,则中止循环
        p+=temp;      // 如果条件不满足则变量自身相加
    }
     
    return p;
}

* 话说这个穷举求最小公倍数的代码跟求最大公约数的又有点区别了,要是我写我肯定直接 Copy 上面最大公约数放下来用两个数乘积除最大公约数来得出最小公倍数了。。。为什么我的脑子就这么喜欢用复制粘贴的呢?

更相减损术

* 这个方法好像在中学学过,在数学教材延伸阅读之类的地方介绍了来传播中华传统文化来着…⑧过我忘的相当干净了。

更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。

让我们来看看《九章算术》是怎么说的:“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”这里说的“等数”就是最大公约数,所以更相减损法也叫等值算法。计算思路是:任意给定两个正整数;判断它们是否都是偶数。若是则用 2 约简;若不是则执行下一步。以 较大的数较小的数 ,接着把所得的 较小的数 比较,并以 较大的数较小的数 。继续这个操作,直到所得的 减数 相等为止。这时,这个相等的数与第一步中约掉的若干个2的乘积就是所求的“等数”,也就是最大公约数。

* 有丶神奇的算法啊!膜拜古老的智慧

写成 C 语言的样子:

#include <stdio.h>
#include <math.h>
 
int main()
{
    /* 一样的就不写了 */
}
 
int gcd(int a,int b)
{
    int i=0,temp,x;
    while(a%2==0&&b%2==0)  // 将 a,b 化至出现奇数
    {
        a/=2;
        b/=2;
        i+=1;
    }
    if(a<b)                // 确定 a,b 大小排序
    {
        temp=a;
        a=b;
        b=temp;
    }
    while(x)               // a,b 之差 x 不为 0 时一直执行
    {
        x=a-b;             // 取“较大的数”与“较小的数”之差
        a=(b>x)?b:x;       // 将“差”与“较小的数”中较大的数存至 a 中
        b=(b<x)?b:x;       // 将“差”与“较小的数”中较小的数存至 b 中
        if(b==(a-b))       // “减数”与“差”相等时结束循环
            break;
    }
 
    if(i==0)               // 第一步无 2 约去时直接输出最后那个 相等的数 
        return b;
    else                   // 取最后那个 相等的数 与前面约去的 2 乘积
        return ((int)pow(2,i)*b);
}
int lcm(int a,int b)
{
    /* 最小公倍数 = 数 a × 数 b ÷ 最大公约数 */
}

辗转相除法(欧几里德算法)

* 在中学课本上也学过,但现在大部分过程已经忘记了(~_~;)

用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数
相当于下面的公式结构:

         |  a                b=0
gcd(a,b)={
         |  gcd(b,a mod b)   b!=0

* 不会用 LaTeX 写公式暂时用这个替代一下吧嘿嘿嘿

又不是不能用
又不是不能用

那么有这个思路就写程序吧:

include <stdio.h>
 
int main()
{
    /* 一样的就不写了 */
}
 
int gcd(int a,int b)
{
    int temp;
    if(a<b)         // 确定 a,b 大小排序
    {
        temp=a;
        a=b;
        b=temp;
    }
    while(b!=0)     // 循环实现辗转相除
    {
        temp=a%b;
        a=b;
        b=temp;
    }
     
    return a;        // 返回最大公约数 a
}
int lcm(int a,int b)
{
    // 利用上面代码先求出最大公约数
    int m,n,temp;
    m=a;             // 保存初始值 a 参与后续计算
    n=b;             // 保存初始值 b 参与后续计算
    if(a<b)
    {
        temp=a;
        a=b;
        b=temp;
    }
    while(b!=0)
    {
        temp=a%b;
        a=b;
        b=temp;
    }
     
    return m*n/a;        // 返回最小公倍数
}

Stein 算法

Stein 算法听起来玄乎,实际上是对辗转相除法(欧几里德算法)的优化。参考百度百科,辗转相除法在计算较大的素数的最大公约数时有明显缺陷。而由 J. Stein 于 1961 年提出的 Stein 算法很好的解决了欧几里德算法的某些缺陷,Stein 算法只有整数的移位和加减法。

一般实际应用中的整数很少会超过 64 位(当然现在已经允许 128 位了),对于这样的整数,计算两个数之间的模是很简单的。对于字长为 32 位的平台,计算两个不超过 32 位的整数的模,只需要一个指令周期,而计算 64 位以下的整数模,也不过几个周期而已。但是对于更大的素数,这样的计算过程就不得不由用户来设计,为了计算两个超过 64 位的整数的模,用户也许不得不采用类似于多位数除法手算过程中的试商法,这个过程不但复杂,而且消耗了很多 CPU 时间。对于现代密码算法,要求计算 128 位以上的素数的情况比比皆是,设计这样的程序迫切希望能够抛弃除法和取模
——《百度百科.词条. Stein 算法》

* 完了,看了看百度百科 Stein 算法 词条和 欧几里德算法 词条,发现自己根本不懂它们。

阐述 Stein 算法的原理需要先理解以下前提:

  • gcd(a,a)=a
    一个数与其自身的公约数仍是其自身。
  • gcd(ka,kb)=k*gcd(a,b)
    最大公约数运算和倍乘运算可以交换。特殊地,当 k=2 时说明两个偶数的最大公约数必然能被 2 整除。
  • gcd(ka,b)=gcd(a,b)(k与b互为质数)
    约掉两个数中只有其中一个数含有的因子不影响最大公约数。特殊地,当 k=2 时说明计算一个偶数和一个奇数的最大公约数时可以先将偶数除以2。

或者可以再简单一点:

对于两个正整数 x,y (事先约定 x<y ):

  • x,y 均为偶数:gcd(x,y)=2*gcd(x/2,y/2)
  • x,y 均为奇数:gcd(x,y)=gcd((x+y)/2,(x-y)/2)
  • x 奇 y 偶:gcd(x,y)=gcd(x,y/2)
  • x 偶 y 奇:gcd(x,y)=gcd(x/2,y) 或 gcd(x,y)=gcd(y,x/2)

参考代码:

* 原帖的代码缩进实在是有毒…还是我 缩进的好啊 呸呸呸,自写自夸

// Stein 算法非递归调用求最大公约数
int Stein(unsigned int x,unsigned int y)
{
    int factor=0;
    int temp;
    if(x<y)
    {
        temp=x;
        x=y;
        y=temp;
    }
    if(0==y)
        return 0;
    while(x!=y)
    {
        if(x&0x1)              // x 为奇数
        {
            if(y&0x1)          // x 和 y 都为奇数
            {
                y=(x-y)>>1;
                x-=y;
            }
            else               // x 为奇数 y 为偶数
            {
                y>>=1;
            }
        }
        else                   // x 为偶数
        {
            if(y&0x1)          // x 为偶数 y 为奇数
            {
                x>>=1;
                if(x<y)
                {
                    temp=x;
                    x=y;
                    y=temp;
                }
            }
            else               //x和y都为偶数
            {
                x>>=1;
                y>>=1;
                ++factor;
            }
        }
    }
 
    return (x<<factor);
}
 
// Stein 算法递归调用求最大公约数
int gcd(int u,int v)
{
    if(u==0)  return v;
    if(v==0)  return u;
    if(~u&1)                     // u是偶数 
    {
        if(v&1)                  // v 是奇数 
            return gcd(u>>1,v);
        else                     // u 和 v 都是偶数 
            return gcd(u>>1,v>>1)<<1;
    }
    if(~v&1)                     // u 是奇数,v 是偶数 
        return gcd(u,v>>1);
    if(u>v)
        return gcd((u-v)>>1,v);
    return gcd((v-u)>>1,u);
}

 

 
至此,计算最大公因数的 4 种算法就写完啦,总有一种合适叭。不行就穷举 XDDD…
写着这篇不知道称不称得上算法的博文,突然就想入一本《算法》书,看到目录上的二叉树就想上去吊一吊嘿嘿嘿…

添加新评论

已有 2 条评论

:aru1: 先mark住大佬

MonsterX MonsterX 回复 @Helo

:aru16: 2333 什么大佬,tan90º!