当前位置：网站首页>Recursive method to realize the greatest common divisor

Recursive method to realize the greatest common divisor

2022-07-27 14:06:00 【Taro paste】

greatest common divisor

The greatest common factor , Also known as the greatest common divisor 、 The greatest common factor , Refers to the common divisor of two or more integers Maximum One of the

There are many ways to find the greatest common divisor ： The prime factor decomposition method 、 Short division 、 division 、 More derogation etc.

Next, we take the rolling division method as an example to find the maximum common divisor of two numbers

division

division ： Division by rotation is a method of finding the greatest common divisor of two natural numbers , It's also called Euclidean algorithm .
for example ：

seek （319,377）：
∵ 319÷377=0（ more than 319）
∴（319,377）=（377,319）;
∵ 377÷319=1（ more than 58）
∴（377,319）=（319,58）;
∵ 319÷58=5（ more than 29）
∴ （319,58）=（58,29）;
∵ 58÷29=2（ more than 0）
∴ （58,29）= 29;
∴ （319,377）=29.

To find the greatest common divisor of several numbers by means of division , You can find out one first Any two numbers Of greatest common divisor , Then find the greatest common divisor and The third number Maximum common divisor of , Go on in turn , Until the last number . The greatest common divisor of the final result , It's the greatest common divisor of all these numbers .

Data analysis

As mentioned above , You can use rolling division （ Euclidean algorithm ） To find the greatest common divisor , Then we can 319,377 these two items. Specific values use The parameters of the function Come on Instead of . Next, look for his rules

The first round

take （319,377） See as （a,b）;

that

319÷377=0（ more than 319） It can be seen as a%b=x ( more than n);

n For the remainder

（319,377）=（377,319）; Be similar to （a,b）= （b,n）;
（ namely b=377,n=319）

Be careful ： second 319 Not at first a=319 Number of numbers , It is a%b Remainder obtained

The second round

377÷319=1（ more than 58） Can be seen as a=377,b=319,a%b=x( more than n);

（377,319）=（319,58）; Be similar to （a,b）= （b,n）;

Compared with the previous round , We can Last round b,n The value of is assigned to the second round a,b, Until the remainder is 0 when ,b For the greatest common divisor ,
Here we can use recursive method to realize
Insert picture description here

Completion code

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script> // division  function measure(a, b) {
       var n = a % b // Take the remainder  if (n == 0) {
       // Determine whether the remainder is 0, by 0 Output b For the greatest common divisor  return b; } else {
       a = b; // The last round of b The value of a b = n; // The last round of n The value of b return measure(a, b); // recursive   Continue to call the function until the remainder n by 0 } } console.log(measure(319, 377));;// 29 </script>
</body>

</html>