How to find the greatest common divisor in Java?

#How to find the greatest common divisor in Java?

Greatest Common Divisor

①Definition

The common divisors of several natural numbers are called these The common divisor of the numbers; the largest one is called the greatest common divisor of these numbers.

②Euclidean division

Also known as "Euclidean algorithm", it is an algorithm for finding the greatest common divisor

Find two numbers Greatest common divisor: If m > n, let remainder remaining = m%n, if the remainder is not 0, then let m = n, n = remainder, continue = m%n again, until remainder = 0, at which time n is Greatest common divisor.

Find the greatest common divisor of multiple numbers: first find the greatest common divisor of two of the numbers, then find the greatest common divisor of this greatest common divisor and the third number, and continue in turn until the last one So far, the final greatest common divisor obtained is the greatest common divisor of the required numbers

③Code implementation

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;    // 返回最大公约数  
    }

The above is the detailed content of How to find the greatest common divisor in Java?. For more information, please follow other related articles on the PHP Chinese website!