对于3个或更多数字最less见的倍数
你如何计算多个数字的最小公倍数?
到目前为止,我只能在两个数字之间进行计算。 但不知道如何扩展它来计算3个或更多的数字。
到目前为止,这是我做到的
LCM = num1 * num2 / gcd ( num1 , num2 )
用gcd是计算数字最大公约数的函数。 使用欧几里德algorithm
但我不知道如何计算3个或更多的数字。
您可以通过迭代计算两个数字的LCM来计算两个以上数字的LCM,即
lcm(a,b,c) = lcm(a,lcm(b,c))
在Python(修改的primes.py )中:
def gcd(a, b): """Return greatest common divisor using Euclid's Algorithm.""" while b: a, b = b, a % b return a def lcm(a, b): """Return lowest common multiple.""" return a * b // gcd(a, b) def lcmm(*args): """Return lcm of args.""" return reduce(lcm, args)
用法:
>>> lcmm(100, 23, 98) 112700 >>> lcmm(*range(1, 20)) 232792560
reduce()
作用就像这样 :
>>> f = lambda a,b: "f(%s,%s)" % (a,b) >>> print reduce(f, "abcd") f(f(f(a,b),c),d)
这是一个ECMA风格的实现:
function gcd(a, b){ // Euclidean algorithm var t; while (b != 0){ t = b; b = a % b; a = t; } return a; } function lcm(a, b){ return (a * b / gcd(a, b)); } function lcmm(args){ // Recursively iterate through pairs of arguments // ie lcm(args[0], lcm(args[1], lcm(args[2], args[3]))) if(args.length == 2){ return lcm(args[0], args[1]); } else { var arg0 = args[0]; args.shift(); return lcm(arg0, lcmm(args)); } }
我只是在Haskell中弄清楚了这一点:
lcm' :: Integral a => a -> a -> a lcm' ab = a`div`(gcd ab) * b lcm :: Integral a => [a] -> a lcm (n:ns) = foldr lcm' n ns
我甚至花时间写我自己的gcd
function,只是在前奏中find它! D.今天有很多的学习:D
一些不需要gcdfunction的Python代码:
from sys import argv def lcm(x,y): tmp=x while (tmp%y)!=0: tmp+=x return tmp def lcmm(*args): return reduce(lcm,args) args=map(int,argv[1:]) print lcmm(*args)
以下是在terminal中的样子:
$ python lcm.py 10 15 17 510
我会去这个(C#):
static long LCM(long[] numbers) { return numbers.Aggregate(lcm); } static long lcm(long a, long b) { return Math.Abs(a * b) / GCD(a, b); } static long GCD(long a, long b) { return b == 0 ? a : GCD(b, a % b); }
只是一些澄清,因为乍一看,它不能清楚地知道这段代码在做什么:
Aggregate是一个Linq扩展方法,所以你不能忘记添加System.Linq到你的引用。
Aggregate获得累积函数,所以我们可以使用IEnumerable上的属性lcm(a,b,c)= lcm(a,lcm(b,c))。 更多关于总结
GCD计算使用欧几里得algorithm 。
lcm的计算使用Abs(a * b)/ gcd(a,b),请参考按最大公约数还原 。
希望这可以帮助,
这里是一个Python单行(不包括导入)返回range(1, 21)
的LCM range(1, 21)
1,21 range(1, 21)
:
Python 2.7:
import fractions reduce(lambda x,y: x*y//fractions.gcd(x, y), range(1, 21))
Python 3.5+:
import functools import math functools.reduce(lambda x,y: x*y//math.gcd(x, y), range(1, 21))
在Python 2和Python 3中 ,运算符优先规则规定*
和//
运算符具有相同的优先级,所以它们从左到右应用。 因此, x*y//z
意味着(x*y)//z
而不是x*(y//z)
。 这两者通常会产生不同的结果。 这对于浮点除法来说并不重要,但是对整数除法也是如此。
这里是Virgil Disgrcece实施的C#端口:
public class MathUtils { /// <summary> /// Calculates the least common multiple of 2+ numbers. /// </summary> /// <remarks> /// Uses recursion based on lcm(a,b,c) = lcm(a,lcm(b,c)). /// Ported from http://stackoverflow.com/a/2641293/420175. /// </remarks> public static Int64 LCM(IList<Int64> numbers) { if (numbers.Count < 2) throw new ArgumentException("you must pass two or more numbers"); return LCM(numbers, 0); } public static Int64 LCM(params Int64[] numbers) { return LCM((IList<Int64>)numbers); } private static Int64 LCM(IList<Int64> numbers, int i) { // Recursively iterate through pairs of arguments // ie lcm(args[0], lcm(args[1], lcm(args[2], args[3]))) if (i + 2 == numbers.Count) { return LCM(numbers[i], numbers[i+1]); } else { return LCM(numbers[i], LCM(numbers, i+1)); } } public static Int64 LCM(Int64 a, Int64 b) { return (a * b / GCD(a, b)); } /// <summary> /// Finds the greatest common denominator for 2 numbers. /// </summary> /// <remarks> /// Also from http://stackoverflow.com/a/2641293/420175. /// </remarks> public static Int64 GCD(Int64 a, Int64 b) { // Euclidean algorithm Int64 t; while (b != 0) { t = b; b = a % b; a = t; } return a; } }'
使用LINQ,你可以写:
static int LCM(int[] numbers) { return numbers.Aggregate(LCM); } static int LCM(int a, int b) { return a * b / GCD(a, b); }
应该添加using System.Linq;
不要忘记处理例外
函数查找lcm的任何数字列表:
def function(l): s = 1 for i in l: s = lcm(i, s) return s
你可以用另一种方法做 – 让n个数字。拿一对连续的数字,并保存在另一个数组中。 这样做在第一次迭代程序做n / 2迭代。然后下一个从0开始拾起对像(0,1),(2,3)等等。计算他们的LCM并存储在另一个数组中。 这样做直到你留下一个数组。 (如果n是奇数,则不可能findlcm)
在R中,我们可以使用包号中的函数mGCD (x)和mLCM (x)来计算整数向量x中所有数的最大公约数和最小公倍数:
library(numbers) mGCD(c(4, 8, 12, 16, 20)) [1] 4 mLCM(c(8,9,21)) [1] 504 # Sequences mLCM(1:20) [1] 232792560
和Scala版本:
def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b) def gcd(nums: Iterable[Int]): Int = nums.reduce(gcd) def lcm(a: Int, b: Int): Int = if (a == 0 || b == 0) 0 else a * b / gcd(a, b) def lcm(nums: Iterable[Int]): Int = nums.reduce(lcm)
只是为了好玩,一个shell(几乎所有的shell)的实现:
#!/bin/sh gcd() { # Calculate $1 % $2 until $2 becomes zero. until [ "$2" -eq 0 ]; do set -- "$2" "$(($1%$2))"; done echo "$1" } lcm() { echo "$(( $1 / $(gcd "$1" "$2") * $2 ))"; } while [ $# -gt 1 ]; do t="$(lcm "$1" "$2")" shift 2 set -- "$t" "$@" done echo "$1"
尝试一下:
$ ./script 2 3 4 5 6
要得到
60
最大的input和结果应该小于(2^63)-1
或壳math将包装。
我正在寻找gcd和lcm的数组元素,并在以下链接中find了一个很好的解决scheme。
https://www.hackerrank.com/challenges/between-two-sets/forum
其中包括以下代码。 gcd的algorithm使用欧几里德algorithm在下面的链接中有很好的解释。
private static int gcd(int a, int b) { while (b > 0) { int temp = b; b = a % b; // % is remainder a = temp; } return a; } private static int gcd(int[] input) { int result = input[0]; for (int i = 1; i < input.length; i++) { result = gcd(result, input[i]); } return result; } private static int lcm(int a, int b) { return a * (b / gcd(a, b)); } private static int lcm(int[] input) { int result = input[0]; for (int i = 1; i < input.length; i++) { result = lcm(result, input[i]); } return result; }
GCD需要对负数进行一些修正:
def gcd(x,y): while y: if y<0: x,y=-x,-y x,y=y,x % y return x def gcdl(*list): return reduce(gcd, *list) def lcm(x,y): return x*y / gcd(x,y) def lcml(*list): return reduce(lcm, *list)
这个怎么样?
from operator import mul as MULTIPLY def factors(n): f = {} # a dict is necessary to create 'factor : exponent' pairs divisor = 2 while n > 1: while (divisor <= n): if n % divisor == 0: n /= divisor f[divisor] = f.get(divisor, 0) + 1 else: divisor += 1 return f def mcm(numbers): #numbers is a list of numbers so not restricted to two items high_factors = {} for n in numbers: fn = factors(n) for (key, value) in fn.iteritems(): if high_factors.get(key, 0) < value: # if fact not in dict or < val high_factors[key] = value return reduce (MULTIPLY, ((k ** v) for k, v in high_factors.items()))
我们正在实施Calculla上的最小公倍数 ,它可以用于任何数量的input,也可以显示这些步骤。
我们所做的是:
0: Assume we got inputs[] array, filled with integers. So, for example: inputsArray = [6, 15, 25, ...] lcm = 1 1: Find minimal prime factor for each input. Minimal means for 6 it's 2, for 25 it's 5, for 34 it's 17 minFactorsArray = [] 2: Find lowest from minFactors: minFactor = MIN(minFactorsArray) 3: lcm *= minFactor 4: Iterate minFactorsArray and if the factor for given input equals minFactor, then divide the input by it: for (inIdx in minFactorsArray) if minFactorsArray[inIdx] == minFactor inputsArray[inIdx] \= minFactor 5: repeat steps 1-4 until there is nothing to factorize anymore. So, until inputsArray contains only 1-s.
就是这样 – 你有你的身高。
LCM既是联想又可交换的。
LCM(A,B,C)= LCM(LCM(A,B),C)= LCM(一,LCM(B,C))
这里是C中的示例代码:
int main() { int a[20],i,n,result=1; // assumption: count can't exceed 20 printf("Enter number of numbers to calculate LCM(less than 20):"); scanf("%d",&n); printf("Enter %d numbers to calculate their LCM :",n); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n;i++) result=lcm(result,a[i]); printf("LCM of given numbers = %d\n",result); return 0; } int lcm(int a,int b) { int gcd=gcd_two_numbers(a,b); return (a*b)/gcd; } int gcd_two_numbers(int a,int b) { int temp; if(a>b) { temp=a; a=b; b=temp; } if(b%a==0) return a; else return gcd_two_numbers(b%a,a); }
方法compLCM取一个向量并返回LCM。 所有的数字在vectorin_numbers内。
int mathOps::compLCM(std::vector<int> &in_numbers) { int tmpNumbers = in_numbers.size(); int tmpMax = *max_element(in_numbers.begin(), in_numbers.end()); bool tmpNotDividable = false; while (true) { for (int i = 0; i < tmpNumbers && tmpNotDividable == false; i++) { if (tmpMax % in_numbers[i] != 0 ) tmpNotDividable = true; } if (tmpNotDividable == false) return tmpMax; else tmpMax++; } }
ES6风格
function gcd(...numbers) { return numbers.reduce((a, b) => b === 0 ? a : gcd(b, a % b)); } function lcm(...numbers) { return numbers.reduce((a, b) => Math.abs(a * b) / gcd(a, b)); }
clc; data = [1 2 3 4 5] LCM=1; for i=1:1:length(data) LCM = lcm(LCM,data(i)) end
对于任何寻找快速工作代码的人,试试这个:
我写了一个函数lcm_n(args, num)
,它计算并返回数组args
中所有数字的lcm。 第二个参数num
是数组中数字的个数。
把所有这些数字放在一个数组args
,然后调用函数lcm_n(args,num);
这个函数返回所有这些数字的lcm。
这里是函数lcm_n(args, num)
:
int lcm_n(int args[], int num) //lcm of more than 2 numbers { int i, temp[num-1]; if(num==2) { return lcm(args[0], args[1]); } else { for(i=0;i<num-1;i++) { temp[i] = args[i]; } temp[num-2] = lcm(args[num-2], args[num-1]); return lcm_n(temp,num-1); } }
该function需要以下两个function才能工作。 所以,只要把它们一起添加就可以了。
int lcm(int a, int b) //lcm of 2 numbers { return (a*b)/gcd(a,b); } int gcd(int a, int b) //gcd of 2 numbers { int numerator, denominator, remainder; //Euclid's algorithm for computing GCD of two numbers if(a > b) { numerator = a; denominator = b; } else { numerator = b; denominator = a; } remainder = numerator % denominator; while(remainder != 0) { numerator = denominator; denominator = remainder; remainder = numerator % denominator; } return denominator; }
int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a%b); } int lcm(int[] a, int n) { int res = 1, i; for (i = 0; i < n; i++) { res = res*a[i]/gcd(res, a[i]); } return res; }
在python中:
def lcm(*args): """Calculates lcm of args""" biggest = max(args) #find the largest of numbers rest = [n for n in args if n != biggest] #the list of the numbers without the largest factor = 1 #to multiply with the biggest as long as the result is not divisble by all of the numbers in the rest while True: #check if biggest is divisble by all in the rest: ans = False in [(biggest * factor) % n == 0 for n in rest] #if so the clm is found break the loop and return it, otherwise increment factor by 1 and try again if not ans: break factor += 1 biggest *= factor return "lcm of {0} is {1}".format(args, biggest)
>>> lcm(100,23,98) 'lcm of (100, 23, 98) is 112700' >>> lcm(*range(1, 20)) 'lcm of (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19) is 232792560'
这是我用过的 –
def greater(n): a=num[0] for i in range(0,len(n),1): if(a<n[i]): a=n[i] return a r=input('enter limit') num=[] for x in range (0,r,1): a=input('enter number ') num.append(a) a= greater(num) i=0 while True: while (a%num[i]==0): i=i+1 if(i==len(num)): break if i==len(num): print 'LCM = ',a break else: a=a+1 i=0
这是PHP的实现:
// https://stackoverflow.com/q/12412782/1066234 function math_gcd($a,$b) { $a = abs($a); $b = abs($b); if($a < $b) { list($b,$a) = array($a,$b); } if($b == 0) { return $a; } $r = $a % $b; while($r > 0) { $a = $b; $b = $r; $r = $a % $b; } return $b; } function math_lcm($a, $b) { return ($a * $b / math_gcd($a, $b)); } // https://stackoverflow.com/a/2641293/1066234 function math_lcmm($args) { // Recursively iterate through pairs of arguments // ie lcm(args[0], lcm(args[1], lcm(args[2], args[3]))) if(count($args) == 2) { return math_lcm($args[0], $args[1]); } else { $arg0 = $args[0]; array_shift($args); return math_lcm($arg0, math_lcmm($args)); } } // fraction bonus function math_fraction_simplify($num, $den) { $g = math_gcd($num, $den); return array($num/$g, $den/$g); } var_dump( math_lcmm( array(4, 7) ) ); // 28 var_dump( math_lcmm( array(5, 25) ) ); // 25 var_dump( math_lcmm( array(3, 4, 12, 36) ) ); // 36 var_dump( math_lcmm( array(3, 4, 7, 12, 36) ) ); // 252
上面的回答(ECMA风格的代码),积分转到@ T3db0t。