3 개 이상의 숫자에 대해 가장 일반적인 배수
https://stackoverflow.com/questions/147515
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
다중 숫자 중 가장 일반적인 배수를 어떻게 계산합니까?
지금까지 나는 두 숫자 사이에서만 계산할 수있었습니다. 그러나 3 개 이상의 숫자를 계산하기 위해 확장하는 방법을 모릅니다.
지금까지 이것이 내가 한 방식입니다
LCM = num1 * num2 / gcd ( num1 , num2 )
GCD를 사용하면 숫자에 대한 가장 큰 공통 디바이저를 계산하는 기능입니다. 유클리드 알고리즘 사용
그러나 3 개 이상의 숫자를 계산하는 방법을 알 수 없습니다.
해결책
두 숫자의 LCM을 반복적으로 계산하여 2 개 이상의 LCM을 계산할 수 있습니다.
lcm(a,b,c) = lcm(a,lcm(b,c))
다른 팁
파이썬에서 (수정 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
// 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));
}
}
나는 이것 (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를 참조에 추가하는 것을 잊을 수 없습니다.
집계는 누적 기능을 가져서, 우리는 ienumerable에 대한 속성 LCM (A, B, C) = LCM (A, LCM (B, C))을 사용할 수 있습니다. 집계에 대한 자세한 내용
GCD 계산을 사용합니다 유클리드 알고리즘.
LCM 계산은 ABS (a*b)/gcd (a, b)를 사용합니다. 가장 큰 공통 구분에 의한 감소.
도움이 되었기를 바랍니다,
방금 Haskell에서 이것을 알아 냈습니다.
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 기능, prelude에서만 찾기 위해서만! 오늘 저를위한 많은 학습 : d
GCD에 대한 기능이 필요하지 않은 일부 파이썬 코드 :
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
다음은 정수의 LCM을 1 ~ 20으로 반환하기위한 파이썬 One-Liner (수입을 계산하지 않음)입니다.
파이썬 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). 두 사람은 일반적으로 다른 결과를 생성합니다. 이것은 플로트 디비전에 중요하지 않았지만 플로어 디비전.
다음은 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;
}
}'
숫자 목록의 LCM을 찾는 기능 :
def function(l):
s = 1
for i in l:
s = lcm(i, s)
return s
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; 예외를 처리하는 것을 잊지 마십시오 ...
여기에 있습니다 빠른.
// 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) }
}
다른 방법으로 할 수 있습니다 - n 숫자가 있도록하십시오. 연속 숫자 쌍을 얻고 다른 배열에 LCM을 저장하십시오. 첫 번째 반복 프로그램 에서이 작업을 수행하면 N/2 반복이 수행됩니다. 다음에 다음은 (0,1), (2,3) 및 on.com에서 LCM을 푸트하고 다른 배열에 보관하는 쌍을 픽업합니다. 하나의 배열이 남을 때 까지이 작업을 수행하십시오. (n이 홀수 인 경우 LCM을 찾을 수 없습니다)
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
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));
}
그리고 스칼라 버전 :
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)
재미를 위해, 쉘 (거의 모든 쉘) 구현 :
#!/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
가장 큰 입력과 결과는보다 적어야합니다 (2^63)-1 또는 쉘 수학이 랩됩니다.
GCD 및 LCM 배열 요소를 찾고 있었고 다음 링크에서 좋은 솔루션을 찾았습니다.
https://www.hackerrank.com/challenges/between-two-sets/forum
여기에는 다음 코드가 포함됩니다. GCD의 알고리즘은 아래 링크에서 잘 설명 된 유클리드 알고리즘을 사용합니다.
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;
}
여기에 있습니다 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 스타일 코드).
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에서 가장 일반적인 배수 단계를 표시하는 모든 입력에 대해서도 작동합니다.
우리가하는 일은 다음과 같습니다.
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 (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);
}
메소드 complcm은 벡터를 가져 와서 LCM을 반환합니다. 모든 숫자는 벡터 in_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++;
}
}
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) 배열의 모든 숫자의 LCM을 계산하고 반환하는 args. 두 번째 매개 변수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) {
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;
}
파이썬에서 :
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 'L.C.M = ',a
break
else:
a=a+1
i=0
파이썬 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)
시간 제약이 없다면, 이것은 상당히 간단하고 간단합니다.
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
