search

Home >Web Front-end >JS Tutorial >How to calculate GCD of two or more numbers/arrays in JavaScript?

How to calculate GCD of two or more numbers/arrays in JavaScript?

WBOY
WBOYforward
2023-09-10 23:13:111176browse

如何在 JavaScript 中计算两个或多个数字/数组的 GCD？

The greatest common divisor (GCD) of two or more numbers, also called the greatest common factor (GCF) or highest common factor (HCF), is The largest positive integer that divides a given value without a remainder. In other words, GCD is the largest divisor of two numbers.

For example, the GCD of 24 and 36 is 12.

How to calculate two numbers?

There are several different ways to calculate the GCD of two numbers, but the most common method is the Euclidean algorithm.

Euclidean algorithm is an iterative method that starts with two numbers a and b and finds the GCD of a and b. The basic idea of ​​Euclidean's algorithm is to continuously subtract a smaller number from a larger number until the two numbers are equal.

  • For example, let us find GCD for 24 and 36 using Euclidean algorithm.

  • Starting with 24 and 36, we subtract the smaller number (24) from the larger number (36) to get 12.

  • Then, we subtract the smaller number (12) from the larger number (24) to get 12.

  • Since these two numbers are now equal, we have found GCD! The GCD in this example is 12.

How to calculate GCD for more than two numbers?

You can also use the Euclidean algorithm to calculate the GCD of more than two numbers. The basic idea is the same as before, but instead of subtracting the smaller number from the larger number, you subtract the GCD of two numbers from the larger number.

  • For example, we find the GCD of 24, 36, and 48.

  • First, we use Euclidean algorithm to find the GCD of 24 and 36, which is 12.

  • Then, we use Euclidean algorithm again The algorithm finds the GCD of 36 and 48, which is 12.

  • Finally, we use the Euclidean algorithm for the last time to find the GCD of 48 and 12, which is 12.

  • Since the GCD of 24, 36 and 48 is 12, we can stop here.

Example

This is a complete working code example of how to calculate the GCD of two or more numbers in JavaScript. 

<!doctype html>
<html>
<head>
   <title>Examples</title>
</head>
<body>
   <h2>Calculating GCD (Greatest Common Divisor)</h2>
   <div id="result1"></div>
   <div id="result2"></div>
   <script>
      function gcd(a, b) {
         // Make sure a is larger than b
         if (a < b) {
            var temp = a;
            a = b;
            b = temp;
         }

         // Iteratively subtract the smaller number from the larger number
         // until the two numbers are equal
         while (b != 0) {
            var temp = b;
            b = a % b;
            a = temp;
         }

         // Return the GCD
         return a;
      }
      // Calculate the GCD of 24 and 36
      var n1 = 24;
      var n2 = 36;
      var result = gcd(n1, n2);
      document.getElementById("result1").innerHTML = `GCD of ${n1} and ${n2} = ` + result;

      // Calculate the GCD of 24, 36, and 48
      var n1 = 8;
      var n2 = 12;
      var n3 = 20;
      var result = gcd(n1, n2, n3);
      document.getElementById("result2").innerHTML = `<br> GCD of ${n1}, ${n2}, and ${n3} =1`+ result;
   </script>
</body>
</html>

Conclusion

In this article, we learned how to calculate the Greatest Common Divisor (GCD) of two or more numbers using Euclidean Algorithm.

The above is the detailed content of How to calculate GCD of two or more numbers/arrays in JavaScript?. For more information, please follow other related articles on the PHP Chinese website!

JavaScript 算法
Statement：
This article is reproduced at:tutorialspoint.com. If there is any infringement, please contact admin@php.cn delete
Previous article：How to create your first chart using FusionCharts.js?Next article：How to create your first chart using FusionCharts.js?

Related articles

See more