Kleinste gemeinsame Vielfache für 3 oder mehr Nummern
https://stackoverflow.com/questions/147515
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wie beurteilen Sie die kleinste gemeinsame Vielfache von mehreren Zahlen berechnen?
Bisher habe ich nur in der Lage gewesen, es zwischen zwei Zahlen zu berechnen. Haben aber keine Ahnung, wie es zu erweitern zu berechnen 3 oder mehr Zahlen.
Bisher ist dies, wie ich es tat
LCM = num1 * num2 / gcd ( num1 , num2 )
Mit GCD ist die Funktion, den größten gemeinsamen Teiler für die Zahlen zu berechnen. Mit euklidischem Algorithmus
Aber ich kann nicht herausfinden, wie es für 3 oder mehr Zahlen zu berechnen.
Lösung
Sie können die LCM von mehr als zwei Zahlen berechnen, indem iterativ die LCM zweier Zahlen Berechnung, d.
lcm(a,b,c) = lcm(a,lcm(b,c))
Andere Tipps
In Python (modifizierte 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)
Verbrauch:
>>> lcmm(100, 23, 98)
112700
>>> lcmm(*range(1, 20))
232792560
reduce() funktioniert so etwas wie dieser :
>>> f = lambda a,b: "f(%s,%s)" % (a,b)
>>> print reduce(f, "abcd")
f(f(f(a,b),c),d)
Hier ist eine ECMA-Stil Umsetzung:
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));
}
}
würde ich mit diesem einem (C #) gehen:
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);
}
Nur einige Präzisierungen, denn auf den ersten Blick nicht so klar ist Nähte, was dieser Code tut:
Aggregate sind eine Linq Extension-Methode, so dass Sie vergessen, können nicht mit System.Linq auf Ihre Referenzen hinzuzufügen.
Aggregate werden eine Akkumulationsfunktion, so können wir von der Eigenschaft LCM (a, b, c) = kgV (a, LCM (b, c)) über eine IEnumerable machen. Mehr auf Aggregate
GCD Berechnung nutzt die euklidische Algorithmus .
lcm Berechnung verwendet Abs (a * b) / ggT (a, b), siehe href="http://en.wikipedia.org/wiki/Least_common_multiple" rel="noreferrer"> Reduktion durch die in .
Hope, das hilft,
ich dies nur heraus in 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
Ich habe sogar die Zeit, meine eigene gcd Funktion zu schreiben, nur es in Prelude zu finden! Viele heute für mich zu lernen: D
Einige Python-Code, der nicht über eine Funktion zum gcd erfordert:
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)
Hier ist, wie es im Terminal aussieht:
$ python lcm.py 10 15 17
510
Hier ist ein Python-Einzeiler (ohne Importe) die LCM der ganzen Zahlen zurück von 1 bis 20 inklusive:
Python 3.5 + Importe:
from functools import reduce
from math import gcd
Python 2.7 Importe:
from fractions import gcd
Gemeinsame Logik:
lcm = reduce(lambda x,y: x*y//gcd(x, y), range(1, 21))
In beiden Python 2 und Python 3 , Betreiber Vorrangregeln diktieren, dass die * und // Betreiber das gleiche haben Vorrang, und so gelten sie von links nach rechts. Als solches bedeutet x*y//z (x*y)//z und nicht x*(y//z). Die beiden erzeugen typischerweise unterschiedliche Ergebnisse. Dies hätte nicht so viel von Bedeutung für Schwimmer Division aber es hat für Boden Division .
Hier ist ein C # Hafen von Virgil Disgr4ce des Implemenation:
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;
}
}'
Funktion LCM jede Liste von Zahlen zu finden:
def function(l):
s = 1
for i in l:
s = lcm(i, s)
return s
LINQ verwenden könnten Sie schreiben:
static int LCM(int[] numbers)
{
return numbers.Aggregate(LCM);
}
static int LCM(int a, int b)
{
return a * b / GCD(a, b);
}
Sollte using System.Linq; hinzuzufügen und vergessen Sie nicht die Ausnahmen zu behandeln ...
Hier ist sie in Swift .
// 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) }
}
Sie können es eine andere Art und Weise tun - Es werde n numbers.Take ein Paar von fortlaufenden Nummern speichern und ihre LCM in einem anderen Array. Tut dies auf dem ersten Iteration Programm tut n / 2 iterations.Then abholen nächstes Paar von 0 gefällt (0,1) ausgehend, (2,3) und so ihre on.Compute LCM und Speicher in einem anderen Array. Tun Sie dies, bis Sie mit einem Array gelassen werden. (Es nicht möglich ist LCM zu finden, wenn n ungerade ist)
R können wir die Funktionen mGCD (x) und MLCM (x) aus dem Paket Zahlen , zu berechnen, die größte gemeinsame Teiler und kleinste gemeinsame Vielfache für alle Zahlen in dem Ganzzahl-Vektor x zusammen:
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 Stil
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));
}
Und die Scala-Version:
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)
Just for fun, eine Schale (fast jede Schale) Umsetzung:
#!/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"
versuchen Sie es mit:
$ ./script 2 3 4 5 6
bekommen
60
Die größte Ein- und Ergebnis sollen weniger als (2^63)-1 oder die Schale math einbettet.
ich suche ggT und kgV von Array-Elementen und eine gute Lösung in dem folgenden Link gefunden.
https://www.hackerrank.com/challenges/between-two -Sets / forum
, die enthält Code folgen. Der Algorithmus für GCD verwendet die euklidische Algorithmus auch in den Link weiter unten erläutert.
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;
}
Hier ist die PHP Implementierung:
// 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
Credits gehen @ T3db0t mit seinem oben (ECMA-Stil-Code) beantworten.
GCD braucht ein wenig Korrektur für negative Zahlen:
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)
Wie wäre das?
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()))
Wir haben funktionierende Implementierung von Kleinstes gemeinsames Vielfaches auf Calculla , die auch für eine beliebige Anzahl von Eingängen arbeitet Anzeige der Schritte.
Was wir tun, ist:
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.
Und das ist es - hast du deine LCM
.LCM ist sowohl assoziativ und kommutativ.
LCM (a, b, c) = LCM (LCM (a, b), c) = LCM (a, LCM (b, c))
Hier ist Beispielcode in 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);
}
Methode compLCM nimmt einen Vektor und gibt LCM. Alle Zahlen sind in Vektor 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
Für alle, für eine schnelle Arbeits Code suchen, versuchen Sie dies:
ich eine Funktion geschrieben lcm_n(args, num) , die die LCM aller Zahlen im Array args berechnet und zurückgibt. Der zweite parameternum ist die Anzahl der Zahlen in der Anordnung.
Setzen Sie all diese Zahlen in einem Array args und rufen dann die Funktion wie lcm_n(args,num);
Diese Funktion zeigt die LCM all diese Zahlen.
Hier ist die Implementierung der Funktion 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);
}
}
Diese Funktion muss unter zwei Funktionen arbeiten. Also, einfach fügen Sie sie zusammen mit ihm.
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;
}
In 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'
Das ist das, was ich gebraucht -
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
für 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)
Wenn es keine Zeitbeschränkung, das ist ziemlich einfach und geradlinig:
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
