[中間アルゴリズム]-最小公倍数
Smallest Common Multiple
トピック
与えられた2つのパラメーターの最小公倍数と、それらの間で割り切れる連番を見つけることができます。
範囲は2つの数値の配列であり、2つの数値は必ずしも番号順になっているとは限りません。
例1と3-すべての中で最小公倍数を1と3で割り切れ、それらの間で割り切れることを見つけます。
促す
テストケース
smallestCommons([1, 5])数値を返す必要があります。smallestCommons([1, 5])60を返すはずです。smallestCommons([5, 1])60を返すはずです。smallestCommons([1, 13])360360を返すはずです。
アイデアの分析
2つの数を掛ける=最小公倍数/最大公約数
したがって、最初のステップは、2つの数値の最大公約数を見つけることです。
コード
gcd（greatest common divisor） scm（smallest common multiple） 注意 ：
ここで、古典的なアルゴリズムについて説明します。最大公約数gcdそして最小公倍数1.// find the greatest common divisor val1 and val2 the (greatest common divisor)
2.// Euclidean algorithm (Euclidean)
3.function gcd(val1,val2){
4. if(val1%val2===0)
5. return val2
6. else
7. return gcd(val2,val1%val2)
8.}
9.
10.function smallestCommons(arr) {
11. // sort in ascending arr
12. arr=arr.sort(function(a,b){
13. return a-b
14. })
15. // find the least common multiple of a and b scm (smallest common multiple)
16. //scm=abs(a*b)/gcd(a,b)
17. var val=arr[0]
18. // find here a plurality of the least common multiple of the number of: obtaining scm1 first two numbers, and then seek scm1 third cycle sequentially number SCM2 ......
19. for(var i=arr[0]+1i<=arr[1]i++){
20. val *=i/gcd(val,i)
21. }
22. return val
23.}
24.
25.smallestCommons([1,5])1.function greatestCommonDivisor(num1, num2) { 2. var retVal = 1 3. 4. for (var i = 2 i <= Math.min(num1, num2) i++) { 5. if (num1 % i === 0 && num2 % i === 0) { 6. retVal = i 7. } 8. } 9. return retVal 10.} 11. 12.function smallestCommons(arr) { 13. var retVal = 1 14. 15. for (var i = Math.min(arr[0], arr[1]) i <= Math.max(arr[0], arr[1]) i++) { 16. retVal = Math.floor(retVal * i / greatestCommonDivisor(retVal, i)) 17. } 18. 19. return retVal 20.} 21. 22.smallestCommons([1,5])（最大公約数）アルゴリズムプロセス（ユークリッドアルゴリズム/ユークリッド）
2つの整数aとbがあります：
①a％bは剰余cを取得しました。つまり、c = a％b
②c= 0の最大公約数の場合、bは2の数です。
③c≠0の場合、a = b、b = c、次に戻って①を実行します。
scmアルゴリズム（最小公倍数アルゴリズム）
= 2つの整数の最小公倍数最大公約数÷積、つまりscm = sqrt（a * b）/ gcd（a、b）In the online version of the largest common multiple search to a classic: