3个或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)

小开

我在哈斯克尔才发现:

lcm' :: Integral a => a -> a -> a
lcm' a b = a`div`(gcd a b) * b
lcm :: Integral a => [a] -> a
lcm (n:ns) = foldr lcm' n ns

我甚至花时间写了我自己的 gcd函数，结果发现它在序曲！今天我学到了很多东西

小开

下面是 ECMA 风格的实现:

function gcd(a, b){
// Euclidean algorithm
while (b != 0){
var temp = b;
b = a % b;
a = temp;
}
return a;
}


function lcm(a, b){
return (a * b / gcd(a, b));
}


function lcmm(args){
// Recursively iterate through pairs of arguments
// i.e. 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));
}
}

小开

你可以用另一种方式设有 n 个数字。取一对连续数字并将其 lcm 保存到另一个数组中。在第一个迭代程序中执行此操作需要进行 n/2次迭代。然后再从0开始选择对，比如(0,1) ，(2,3)等等。计算它们的 LCM 并存储在另一个数组中。这样做，直到只剩下一个数组。 (如果 n 是奇数，就不可能找到 lcm)

小开

一些不需要 gcd 函数的 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)

这是航站楼的样子:

$ python lcm.py 10 15 17
510

小开

下面是 Virgil Disgr4ce 实现的 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
// i.e. 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;
}
}'

小开

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()))

小开

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));
}

小开

使用 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;并且不要忘记处理异常..。

小开

clc;


data = [1 2 3 4 5]


LCM=1;


for i=1:1:length(data)


LCM = lcm(LCM,data(i))


end

小开

我们有工作实现微积分的最小公倍数的工作任何数量的输入也显示的步骤。

我们要做的是:

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 既是联想的又是可交换的。

LCM (a，b，c) = LCM (a，b) ，c) = LCM (a，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);
}

小开

在 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

小开

我会选择这个(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);
}

只是一些澄清，因为乍一看，似乎不太清楚这段代码在做什么:

聚合是一个 Linq 扩展方法，因此您不能忘记使用 System.Linq 添加引用。

聚合得到一个累加函数，因此我们可以利用 IEnumable 上的 lcm (a，b，c) = lcm (a，lcm (b，c))属性。更多关于总计

GCD 计算利用辗转相除法。

Lcm 计算使用 Abs (a * b)/gcd (a，b) ，请参阅减少最大公约数。

希望这对你有帮助,

小开

方法 compLCM 获取一个向量并返回 LCM。

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++;
}
}

小开

对于寻找快速工作代码的人，请尝试以下方法:

我编写了一个函数 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);
}
}

这个函数需要以下两个函数才能正常工作。

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){ 如果(b = = 0)返回 a; 返回 gcd (b，a% b) ; } Int lcm (int [] a，int n){ Int res = 1，i; (i = 0; i < n; i + +){ Res = res * a [ i ]/gcd (res，a [ i ]) ; } 返还利息; }

小开

下面是一个 Python 一行程序(不包括导入) ，它返回从1到20的整数的 LCM，包括:

Python 3.5 + 导入:

from functools import reduce
from math import gcd

Python 2.7导入:

from fractions import gcd

常见的逻辑:

lcm = reduce(lambda x,y: x*y // gcd(x, y), range(1, 21))

请注意，在巨蟒2和巨蟒3中，操作符优先级规则规定 *和 //操作符具有相同的优先级，因此它们从左到右应用。因此，x*y // z的意思是 (x*y) // z而不是 x * (y//z)。这两者通常会产生不同的结果。这对于浮点除法来说不是很重要，但是对于楼层分隔部来说很重要。

小开

而 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)

小开

函数查找任意数字列表的 lcm:

 def function(l):
s = 1
for i in l:
s = lcm(i, s)
return s

小开

只是为了好玩，一个 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

得到

最大的输入和结果应该小于 (2^63)-1，否则 shell 数学就会自动换行。

小开

在巨蟒中:

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'

小开

我正在寻找数组元素的 gcd 和 lcm，并在下面的链接中找到了一个很好的解决方案。

Https://www.hackerrank.com/challenges/between-two-sets/forum

Gcd 的算法使用以下辗转相除法已在以下连结详细解释。

Https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-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;
}

小开

这是我用的..

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 'L.C.M = ',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
// i.e. 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

信用卡到@T3db0t 与他的上面的答案(ECMA 风格的代码)。

小开

这是 斯威夫特。

// Euclid's algorithm for finding the greatest common divisor
func gcd(_ a: Int, _ b: Int) -> Int {
let r = a % b
if r != 0 {
return gcd(b, r)
} else {
return b
}
}


// Returns the least common multiple of two numbers.
func lcm(_ m: Int, _ n: Int) -> Int {
return m / gcd(m, n) * n
}


// Returns the least common multiple of multiple numbers.
func lcmm(_ numbers: [Int]) -> Int {
return numbers.reduce(1) { lcm($0, $1) }
}

小开

如果没有时间限制，这是相当简单和直接的:

def lcm(a,b,c):
for i in range(max(a,b,c), (a*b*c)+1, max(a,b,c)):
if i%a == 0 and i%b == 0 and i%c == 0:
return i

小开

对于 python 3:

from functools import reduce


gcd = lambda a,b: a if b==0 else gcd(b, a%b)
def lcm(lst):
return reduce(lambda x,y: x*y//gcd(x, y), lst)

小开

在 Ruby 中，它就像这样简单:

> [2, 3, 4, 6].reduce(:lcm)
=> 12


> [16, 32, 96].reduce(:gcd)
=> 16

(在 Ruby 2.2.10和2.6.3上测试)

小开

Python 3.9 math模块的 gcd和 lcm对数字列表的支持。

import math


lst = [1,2,3,4,5,6,7,8,9]


print(math.lcm(*lst))


print(math.gcd(*lst))