当前位置:首页 > C++知识 > 正文内容

【初级篇】求最大公约数的方法

亿万年的星光5年前 (2021-01-28)C++知识21280

1.辗转相除法

int gcd(int a,int b)

 { 
     if(a%b==0)
         return b;
     else
         return gcd(b,a%b);
 }

2.穷举法

int divisor (int a, int b) //自定义函数求两数的最大公约数

 {
      int  temp;//定义整型变量
     temp=(a>b)?b:a;//采种条件运算表达式求出两个数中的最小值
     while(temp>0)

      {
              if(a%temp==0&&b%temp==0)//只要找到一个数能同时被a,b所整除,则中止循环
              break;
              temp--;//如不满足if条件则变量自减,直到能被a,b所整除 
      } 
     return (temp);//返回满足条件的数到主调函数处 
  }

3.更相减损法

 int gcd2(int m,int n)
 {
     int i=0,temp,x;
     while(m%2==0&&n%2==0)//判断m和n能被多少个2整除
    {
         m/=2;
         n/=2;
         i+=1;
    } 
     if(m<n)//m保存大的值
   {
        temp=m;
        m=n;
        n=temp;
   } 
     while(x)
   {
        x=m-n;
        m=(n>x)?n:x;
        n=(n<x)?n:x;
        if(n==(m-n))
        break;
   }
    if(i==0)
    return n;
        else
        return (int) pow(2,i)*n;
  }

4.其他方法

int gcd(int a,int b)
{
    int c;
    while(b)
    {
        c=a%b;
        a=b;b=c;
    }
    return a;
}


关于最大公约数的一些结论:(不对)

求Sa(a1*a2*a3*a4*a5...)和Sb(b1*b2*b3*b4*b5...)的最大公约数

等于他们对应每一项的最大公约数的乘积。比如:

Sa=(4*3*1*5)=60

Sb=(2*6*2*3)=72

60和72的最大公约数是12。如果把他们单独拆开后,上下每一项对于的最大公约数分别是

2*3*2*1=12。结论一致。在计算中可以用这个公式,来缩小计算数的大小。

扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

2021 年青岛市程序设计竞赛试题(小学组)决赛

2021 年青岛市程序设计竞赛试题(小学组)决赛

1.方程求解【描述】输入正整数 a,b,c。求有多少组 x 和 y 满足 a*x+b*y=c 。x 和 y 都是非负整数。【输入】一行,包含三个正整数 a,b,c,两个整数之间用单个空格隔开。【输出】...

指针(二):指针与数组

1.指针与数组的关系    指向数组的指针变量称为数组指针变量。“数组是内存上一块连续的空间”。数组名就是这块连续空间的首地址。2.指针指向数组  &...

最小生成树(1)

最小生成树(1)

一、定义一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出...

C++链表结构——单链表

0.前言存储方式分为顺序存储结构和链式存储结构。顺序存储结构的优缺点:优点:可以通过一个简单的公式随机存取表中的任一元素,逻辑关系上相邻的两个元素在物理位置上也是相邻的,且很容易找到前驱跟后继元素。缺...

【贪心】区间选点

【贪心】区间选点

【题目描述】数轴上有n个闭区间[ai, bi],取尽量少的点,使得每个区间内都至少有一个点。(不同区间内含的点可以是同一个,1<=n<=10000,1<=ai<=bi<=...

C++中的宏

一、预处理和编译器    首先,预编译器就是在编译器之前运行,换句话说,预编译器根据程序员的指示,决定实际要编译的内容。预编译器编译指令都以 # 开头。例如:1...