java怎麼求最大公約數？

java怎麼求最大公約數？

最大公約數

①定義

幾個自然數公有的約數，叫做這幾個數的公約數；其中最大的一個，叫做這幾個數的最大公約數。

②輾轉相除法

又稱“歐幾里德演算法”，是求最大公約數的演算法

求兩個數的最大公約數：如果m > n，令餘數remainder = m%n，如果餘數不為0，則令m = n， n = remainder，再次remainder = m%n，直到remainder = 0，此時n就是最大公約數。

求多個數的最大公約數：先求出其中兩個數的最大公約數，再求這個最大公約數與第三個數的最大公約數，依序求下去，直到最後一個為止，最後所得的那個最大公約數，就是所求的幾個數的最大公約數

#③程式碼實作

public static int maxCommonDivisor(int m, int n) {  
        if (m < n) {     // 保证被除数大于除数
            int temp = m;  
            m = n;  
            n = temp;  
        }  
        while (m % n != 0) {  // 在余数不能为0时,进行循环  
            int temp = m % n;  
            m = n;  
            n = temp;  
        }  
        return n;    // 返回最大公约数  
    }

以上是java怎麼求最大公約數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！