How to find the least common multiple and greatest common divisor in JS-JS Tutorial-php.cn

This time I will show you how to find the least common multiple and the greatest common divisor with JS. What are the precautions for finding the least common multiple and the greatest common divisor with JS. The following is a practical case. Let’s take a look. .

The method comes from a transformation algorithm for finding the least common multiple of multiple numbers (see the appendix for details)

The algorithm for the least common multiple is transformed from the greatest common divisor. The greatest common divisor can be obtained through the following steps:

(1) Find the minimum non-zero term aj in a1, a2,...,an. If there are multiple minimum non-zero terms, choose any

(2) All other non-0 items ak except aj are replaced with ak mod aj; if there are no other non-0 items except aj, go to (4)
(3) Go to (1)
(4) The greatest common divisor of a1, a2,...,an is aj

I wrote two versions of

javascript to find the common multiples and common divisors, mainly focusing on the algorithm and not paying much attention to it. Naming, many just write single-letter names directly.

0. Simple and easy to understand loop

function getMin(arr){
  var min = Infinity
  arr.forEach(function(item){
    if( item < min && item !=0 ){
      min = item
    }
  })
  return min
}
function howMuchZero(arr){
  var zerocount = 0
  arr.forEach( function(item){
    item === 0 ?
    zerocount++ : zerocount
  }
    )
  if(zerocount === arr.length -1) {
    return true
  }
  else return false
}
function maxpi(arr){
  do {
  var min = getMin(arr)
  arr = arr.map((item)=> item===min? item:item%min
    )
  }
  while (!howMuchZero(arr))
  return getMin(arr)
}
function minMulti(arr){
  var totalMulti = arr.reduce((pre,item)=>
    pre = pre * item
    )
  var brr = arr.map((item)=>
    totalMulti/item
    )
  var brr_maxpi = maxpi(brr)
  return totalMulti/brr_maxpi
}

Copy after login

1. function within function

var arr_minMulti, arr_maxpi
function minMulti(arr){
  var totalmulti =
    arr.reduce((multi,curvalue) => multi * curvalue)
  if (totalmulti === 0) {
    arr_minMulti = 0
    return
  }
  var marr = arr.map((item) => totalmulti/item)
  maxpisor(marr)
   arr_minMulti = totalmulti / arr_maxpi
}
function maxpisor(arr){
  var min = getMin(arr)
  if(min === Infinity) {
    arr_maxpi = min
    return
  }
  var exparr = arr.filter(function(item){
      return (item !== min && item !== 0)
  })
  if(exparr.length === 0){
    arr_maxpi = min
    return;
  }
  else{
    var modearr = arr.map(function(item){
      return (item === min||item===0)? item:item%min
    })
    console.log(modearr,'modearr')
    maxpisor(modearr)
  }
}
function getMin(arr){
  var min = Infinity
  arr.forEach(function(item){
    if (item && item < min) {
      min = item
    }
  })
  return min
}
arr =[13,20,10,26]
minMulti(arr)
console.log(&#39;最小公倍数&#39;,arr_minMulti)

Copy after login

2. object oriented Object-oriented

function maxpisor(arr,origin){
  this.arr = arr
  this.min = this._getMin(arr)
  this.maxpisor = this._getMaxp()
  if(origin){
    this.minMulti = this._getMinMulti()
  }
}
maxpisor.prototype._getMin = function(arr) {
  var min = Infinity
  arr.forEach(item => min = (item && item < min)? item : min)
  return min
}
maxpisor.prototype._getMaxp = function() {
  var arr_maxpi
  var self = this,
    arr = this.arr
  function maxpisor(arr){
    //console.log(self._getMin)
    var min = self._getMin.call(null,arr)
     console.log(min,&#39;min&#39;)
    if(min === Infinity) {
      arr_maxpi = 0
      return ;
    }
    var exparr = arr.filter( item => (item !== min && item != 0) )
    if(exparr.length === 0){
      arr_maxpi = min
      return;
    }
    else{
      var modearr = arr.map(item =>
        (item === min || item === 0)? item : item % min
      )
      maxpisor(modearr)
      }
  }
  maxpisor(this.arr)
  return arr_maxpi
}
maxpisor.prototype._getMinMulti = function(){
  var arr = this.arr,
    arr_minMulti
  var totalmulti =
    arr.reduce((multi,curvalue) => multi * curvalue)
  if (totalmulti === 0) {
    return 0
  }
  else {
    var marr = arr.map((item) => totalmulti/item),
    b = new maxpisor(marr,false)
    arr_minMulti = totalmulti / b.maxpisor
    return arr_minMulti
  }
}
var a = new maxpisor([12,9,6],true)
console.log(a)

Copy after login

Appendix: Analysis of the principle of a transformation algorithm for finding the least common multiple of multiple numbers

Let [a1,a2,..,an] represent the least common multiple of a1,a2,..,an, (a1,a2,..,an) represent the greatest common divisor of a1,a2,..,an, Among them, a1, a2,...,an are non-negative integers. For two numbers a, b, [a, b] = ab/(a, b), so the least common multiple of the two numbers can be calculated using their greatest common divisor. But for multiple numbers, [a1,a2,..,an]=M/(a1,a2,..,an) does not hold, and M is the product of a1,a2,..,an. For example: [2,3,4] is not equal to 24/(2,3,4). That is, the relationship between the greatest common divisor and the least common multiple of two numbers cannot be simply extended to the case of n numbers.

The relationship between the least common multiple of multiple numbers and the greatest common divisor of multiple numbers is discussed here. Extend the relationship between the greatest common divisor and the least common multiple of two numbers to the case of n numbers. On this basis, the vector transformation algorithm for finding the greatest common divisor of n numbers is used to calculate the least common multiple of multiple numbers.

1. The relationship between the least common multiple of multiple numbers and the greatest common divisor of multiple numbers

Let p be the prime factor of one or more numbers in a1, a2,...,an, a1, a2, .., the degrees of an with respect to p are r1, r2, .., rn respectively. The maximum value among r1, r2, .., rn is rc1=rc2=..=rcm=rmax, and the minimum value is rd1=rd2= ..=rdt=rmin, that is, the degree of p contained in m numbers in r1, r2, .., rn is the maximum value, and the degree of p contained in t numbers is the minimum value. For example: the degrees of the prime factor 2 in 4, 12, and 16 are 2, 2, and 4 respectively. There is a number that contains the degree of 2 as the maximum value, and there are 2 numbers that contain the degree of 2 as the minimum value; regarding the prime The degrees of factor 3 are 0, 1, and 0 respectively. One number contains the degree of 3 as the maximum value, and there are 2 numbers containing the degree of 3 as the minimum value.

For the greatest common divisor, it only includes prime factors contained in a1, a2,...,an, and the degree of each prime factor is the lowest degree of the prime factor in a1, a2,...,an , the lowest degree is 0, which means it does not contain [1].

For the least common multiple, it only includes the prime factors contained in a1, a2,...,an, and the degree of each prime factor is the highest degree of the prime factor in a1, a2,...,an [ 1].

Theorem 1: [a1,a2,..,an]=M/(M/a1,M/a2,..,M/an), where M is a1,a2,..,an The product of a1, a2,...,an is a positive integer.

For example: for 4,6,8,10, there are [4,6,8,10]=120, and M=4*6*8*10=1920, M/(M/a1, M/a2,..,M/an) =1920/(6*8*10,4*8*10,4*6*10,4*6*8)=1920/16=120.

Proof:

The degree of p in M/a1,M/a2,..,M/an is greater than or equal to r1 r2 ..rn-rmax, and the degree of p is equal to r1 r2 .. rn-rmax. This is because

(1) The degree of p in M/ai is r1 r2 .. rn-ri, so the minimum degree of p in M/a1, M/a2,.., M/an is r1 r2 .. rn-rmax.

(2) For the item aj (one or more items) with the largest degree of p in a1, a2,..,an, the degree of p in M/aj is r1 r2 .. rn-rmax.

Or for the term aj with the largest degree of p in a1, a2,..,an, the degree of p in M/aj is less than or equal to M/ak, where ak is in a1,a2,..,an One of the n-1 terms except aj, and the degree of p in M/aj is r1 r2 .. rn-rmax.

Therefore, the degree of p in (M/a1,M/a2,..,M/an) is r1 r2 .. rn-rmax, so M/(M/a1,M/a2,. .,M/an) the degree of p is rmax.

The above p does not impose any restrictions. Since all prime factors contained in a1, a2,..,an are of the highest degree in a1,a2,..,an in M/(M/a1,M/a2,..,M/an), Therefore, [a1,a2,..,an]=M/(M/a1,M/a2,..,M/an) is established.

Get certified.

Theorem 1 for 2 numbers is [a,b]=ab/(ab/a,ab/b)=ab/(b,a)=ab/(a,b), that is, [a, b]=ab/(a,b). Therefore, Theorem 1 is an extension of the least common multiple formula of two numbers [a, b] = ab/(a, b). Theorem 1 can be used to transform finding the least common multiple of multiple numbers into finding the greatest common divisor of multiple numbers.

2. Algorithm implementation of the greatest common divisor of multiple numbers

According to Theorem 1, finding the lowest common multiple of multiple numbers can be transformed into finding the greatest common divisor of multiple numbers. The traditional method to find the greatest common divisor of multiple numbers (a1, a2,..,an) is to find the greatest common divisor of two numbers multiple times, that is,

(1) Use the euclidean division method [2] Calculate the greatest common divisor (a1, a2) of a1 and a2

(2) Use the euclidean division method to calculate the greatest common divisor of (a1, a2) and a3, and obtain (a1, a2, a3)

(3) Use the euclidean method to calculate the greatest common divisor of (a1, a2, a3) and a4, and obtain (a1, a2, a3, a4)

(4) Repeat this, Until (a1,a2,..,an)

is obtained, the above method requires n-1 euclidean division operations.

This article extends the Euclidean division method of two numbers to the Euclidean division method of n numbers, that is, using the Euclidean division method of n numbers once to calculate the greatest common divisor of n numbers. The basic method is to use repeated Euclidean division. The minimum number modulo other numbers is calculated based on the following theorem 2.

Theorem 2: Multiple non-negative integers a1, a2,..,an, if aj>ai, i is not equal to j, then replace aj with aj-ai in a1, a2,..,an , its greatest common divisor remains unchanged, that is (a1,a2,..,aj-1,aj,aj 1,..an)=(a1,a2,..,aj-1,aj-ai,aj 1, ..an).

For example: (34,24,56,68)=(34,24,56-34,68)=(34,24,22,68).

Proof:

According to the commutative law and associative ratio of the greatest common divisor, there are

(a1,a2,..,aj-1,aj,aj 1,. .an)= ((ai,aj),(a1,a2,..,ai-1,ai 1,..aj-1,aj 1,..an)) (i>j case), or

(a1,a2,..,aj-1,aj,aj 1,..an)= ((ai,aj),(a1,a2,..,aj-1,aj 1,.. ai-1,ai 1,..an)) (i

And for (a1,a2,..,aj-1,aj-ai,aj 1,..an), there is

(a1,a2,..,aj-1 ,aj-ai,aj 1,..an)= ((ai, aj-ai),( a1,a2,..,ai-1,ai 1,.. aj-1,aj 1,..an) ) (i>j case), or

(a1,a2,..,aj-1,aj-ai,aj 1,..an)= ((ai, aj-ai),( a1 ,a2,..,aj-1,aj 1,.. ai-1,ai 1,..an)) (i

So just prove that (ai, aj) = (ai, aj-ai).

Since (aj-ai) = aj-ai, any common factor of ai, aj must also be a factor of (aj-ai), that is, it is also a common factor of ai, (aj-ai). Since aj = (aj-ai) ai, any common factor of ai, (aj-ai) must also be a factor of aj, that is, it is also a common factor of ai, aj. Therefore, the greatest common divisor of ai, aj and the greatest common divisor of ai, (aj-ai) must be equal, that is, (ai, aj) = (ai, aj-ai) holds.

Get certified.

Theorem 2 is similar to the elementary transformation of a matrix, that is,

Let the greatest common divisor of a vector be the greatest common divisor of each component of the vector. For vectors , transform: subtract one component from another component, and the new vector is equal to the greatest common divisor of the original vector.

To find the greatest common divisor of multiple numbers, use the method of repeatedly modulating other numbers with the smallest number, that is, subtract other numbers with the smallest number multiple times until a remainder smaller than the smallest number is left. Let n positive integers be a1, a2,...,an. The algorithm for finding the largest common divisor of multiple numbers is described as:

(1) Find the smallest non-zero number among a1, a2,...,an Zero term aj, if there are multiple minimum non-zero terms, choose any one

(2) All other non-zero terms ak except aj are replaced by ak mod aj; if there are no other non-zero terms except aj , then go to (4)

(3) Go to (3)

(4) the greatest common divisor of a1, a2,...,an is aj

For example: for 5 numbers 34, 56, 78, 24, 85, there are

(34, 56, 78, 24, 85)=(10,8,6,24,13)=(4, 2,6,0,1)=(0,0,0,0,1)=1,

For the 6 numbers 12, 24, 30, 32, 36, 42, there are

(12, 24, 30, 32, 36, 42)=(12,0,6,8,0,6)=(0,0,0,2,0,6)=(0,0,0 ,2,0,0)=2.

3. Algorithm implementation of the minimum common multiple of multiple numbers

The algorithm for finding the minimum common multiple of multiple numbers is:

(1) Calculation m=a1*a2*..*an

(2) Replace all items ai in a1, a2,..,an with m/ai

(3) Find a1 ,a2,..,the minimum non-zero term aj in an, if there are multiple minimum non-zero terms, choose one

(4) All other non-zero terms aj except aj are replaced by ak mod aj ;If there are no other non-0 items except aj, go to (6)

(5) Go to (3)

(6) The least common multiple is m/aj

The above algorithm was programmed in a high-level language in the VC environment. Through multiple groups of examples of finding the least common multiple of 5 random numbers, it was compared with the standard method. Compare and verify its correctness. The standard calculation method is: finding the least common multiple of five random numbers is obtained by finding the least common multiple of two numbers 4 times, and the least common multiple of two numbers is obtained by finding the greatest common divisor of the two numbers.

5. Conclusion

Calculating the least common multiple of multiple numbers is a common basic operation. The least common multiple of n numbers can be expressed as the greatest common divisor of other n numbers, so it can be calculated by finding the greatest common divisor of multiple numbers. To find the greatest common divisor of multiple numbers, you can use the vector conversion algorithm to find it all at once.

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website!