首页 > 编程语言 > 详细

欧几里得算法

时间:2019-11-22 01:02:58      阅读:121      评论:0      收藏:0      [点我收藏+]

一、背景及介绍

  在数学中,辗转相除法,又称欧几里得算法(英语:Euclidean algorithm),是求最大公约数的算法。两个整数最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数最大公约数等于其中较小的数两数相除余数的最大公约数。例如,252和105的最大公约数是21(252 = 21 × 12;105 = 21 × 5);因为 252 − 105 = 21 × (12 − 5) = 147 ,所以147和105的最大公约数也是21。

二、递归与非递归实现

 1     /**
 2      * 递归实现
 3      * @param m
 4      * @param n
 5      * @return
 6      */
 7     public static int gcdRecu(int m, int n) {
 8         if (n == 0) {
 9             return m;
10         } else {
11             return gcdRecu(n, m%n);
12         }
13     }
14 
15     /**
16      * 迭代法
17      * @param m
18      * @param n
19      * @return
20      */
21     public static int gcdIter(int m, int n) {
22         int t = 1;
23         while (t != 0) {
24             t = m % n;
25             m = n;
26             n = t;
27         }
28         return m;
29     }

 

 

 

欧几里得算法

原文:https://www.cnblogs.com/magic-sea/p/11907454.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!