【欧几里算法】寻找两数的最大公约数

目的：寻找两数的最大公约数；

描述：有两个非负整数p和q，若q是0，则两数的最大公约数是p；否则，将p除以q得到余数r，q和p的最大公约数即为q和余数r的最大公约数；

注意：任何正整数都是零的约数；
算法描述：

 public static int fun(int p ,int q)
{       
              if(q==0)     //如果q=0，则最大公约数为p
                   return p;
              int r=p%q;                                        
              return fun(q,r);
}

举例：求12和18的最大公约数；

public static void main(String args[])  //求12和18的最大公约数
{
          System.out.println(fun(12,18));
}

结果：
image
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容