JS obtains the least common multiple and greatest common divisor

This time I will bring you JS to obtain the least common multiple and the greatest common divisor. What are the precautions for obtaining the least common multiple and the greatest common divisor with JS? The following is a practical case, let's take a look.

(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

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
}

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)

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)

Appendix: Analysis of the principle of a transformation algorithm for finding 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

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!

Recommended reading:

Detailed explanation of JS callback function usage cases

Detailed explanation of common addition, deletion, modification and query operations of JS DOM elements

The above is the detailed content of JS obtains the least common multiple and greatest common divisor. For more information, please follow other related articles on the PHP Chinese website!