Il minimo comune multiplo per 3 o più numeri
Domanda
Come si calcola il minimo comune multiplo di più numeri?
Finora sono stato in grado di calcolarlo solo tra due numeri. Ma non hai idea di come espanderlo per calcolare 3 o più numeri.
Finora è così che l'ho fatto
LCM = num1 * num2 / gcd ( num1 , num2 )
Con gcd è la funzione per calcolare il massimo comune divisore per i numeri. Utilizzo dell'algoritmo euclideo
Ma non riesco a capire come calcolarlo per 3 o più numeri.
Soluzione
Puoi calcolare l'LCM di più di due numeri calcolando iterativamente l'LCM di due numeri, ad esempio
lcm(a,b,c) = lcm(a,lcm(b,c))
Altri suggerimenti
In Python (modificato 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)
Utilizzo:
>>> lcmm(100, 23, 98)
112700
>>> lcmm(*range(1, 20))
232792560
reduce()
funziona come che :
>>> f = lambda a,b: "f(%s,%s)" % (a,b)
>>> print reduce(f, "abcd")
f(f(f(a,b),c),d)
Ecco un'implementazione in stile 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));
}
}
Vorrei andare con questo (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);
}
Solo alcuni chiarimenti, perché a prima vista non sembra così chiaro cosa stia facendo questo codice:
Aggregate è un metodo di estensione Linq, quindi non puoi dimenticare di aggiungere usando System.Linq ai tuoi riferimenti.
L'aggregato ottiene una funzione di accumulo in modo che possiamo usare la proprietà mcm (a, b, c) = mcm (a, mcm (b, c)) su un IEnumerable. Altre informazioni su Aggregate
Il calcolo GCD si avvale dell'alto algoritmo euclideo .
Il calcolo mcm utilizza Abs (a * b) / gcd (a, b), fare riferimento a Riduzione del massimo comune divisore .
Spero che questo aiuti,
L'ho appena capito 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
Mi sono anche preso il tempo di scrivere la mia funzione gcd
, solo per trovarla in Prelude! Molto apprendimento per me oggi: D
Alcuni codici Python che non richiedono una funzione per 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)
Ecco come appare nel terminale:
$ python lcm.py 10 15 17
510
Ecco un one-liner di Python (senza contare le importazioni) per restituire il LCM degli interi da 1 a 20 inclusi:
Importazioni Python 3.5+:
from functools import reduce
from math import gcd
Importazioni Python 2.7:
from fractions import gcd
Logica comune:
lcm = reduce(lambda x,y: x*y//gcd(x, y), range(1, 21))
In entrambi Python 2 e Python 3 , le regole di precedenza dell'operatore impongono che *
e //
gli operatori hanno la stessa precedenza e quindi si applicano da sinistra a destra. Pertanto, x*y//z
significa (x*y)//z
e non x*(y//z)
. I due in genere producono risultati diversi. Questo non avrebbe avuto importanza per la divisione float, ma lo è per divisione del pavimento .
Ecco una porta C # dell'attuazione di Virgil Disgr4ce:
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;
}
}'
Funzione per trovare mcm di qualsiasi elenco di numeri:
def function(l):
s = 1
for i in l:
s = lcm(i, s)
return s
Usando LINQ puoi scrivere:
static int LCM(int[] numbers)
{
return numbers.Aggregate(LCM);
}
static int LCM(int a, int b)
{
return a * b / GCD(a, b);
}
Dovrebbe aggiungere using System.Linq;
e non dimenticare di gestire le eccezioni ...
Eccolo 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) }
}
puoi farlo in un altro modo - Lascia che ci siano n numeri. Prendi una coppia di numeri consecutivi e salva i suoi mcm in un altro array. In questo modo al primo programma di iterazione vengono eseguite n / 2 iterazioni, quindi si preleva la coppia successiva a partire da 0 come (0,1), (2,3) e così via. Calcolare il LCM e archiviarlo in un altro array. Fallo finché non ti rimane un array. (non è possibile trovare mcm se n è dispari)
In R, possiamo usare le funzioni mGCD (x) e mLCM (x) dal pacchetto numeri , per calcolare il massimo divisore comune e multiplo minimo comune per tutti i numeri nel vettore intero x insieme:
library(numbers)
mGCD(c(4, 8, 12, 16, 20))
[1] 4
mLCM(c(8,9,21))
[1] 504
# Sequences
mLCM(1:20)
[1] 232792560
stile 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));
}
E la versione 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)
Solo per divertimento, un'implementazione della shell (quasi qualsiasi 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"
provalo con:
$ ./script 2 3 4 5 6
per ottenere
60
L'input e il risultato più grandi dovrebbero essere inferiori a (2^63)-1
o la matematica della shell andrà a capo.
stavo cercando gcd e mcm di elementi array e ho trovato una buona soluzione nel seguente link.
https://www.hackerrank.com/challenges/between-two -Imposta / forum
che include il seguente codice. L'algoritmo per gcd utilizza l'algoritmo euclideo spiegato bene nel link sottostante.
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;
}
Ecco l'implementazione 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
I crediti vanno a @ T3db0t con la sua risposta sopra (codice stile ECMA) .
GCD necessita di una piccola correzione per i numeri negativi:
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)
Che ne dici di questo?
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()))
Abbiamo un'implementazione funzionante del minimo comune multiplo su Calculla che funziona anche con qualsiasi numero di input mostrando i passaggi.
Quello che facciamo è:
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.
Ed ecco fatto: hai il tuo mcm.
LCM è sia associativo che commutativo.
LCM (a, b, c) = LCM (LCM (a, b), c) = LCM (a, LCM (b, c))
ecco il codice di esempio 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);
}
Metodo compLCM prende un vettore e restituisce LCM. Tutti i numeri sono all'interno di vector 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
Per chiunque cerchi un codice di lavoro rapido, prova questo:
Ho scritto una funzione lcm_n(args, num)
che calcola e restituisce il mcm di tutti i numeri nell'array args
. Il secondo parametro num
è il conteggio dei numeri nell'array.
Metti tutti quei numeri in un array lcm_n(args,num);
e poi chiama la funzione come <=>
Questa funzione restituisce il mcm di tutti quei numeri.
Ecco l'implementazione della funzione <=>:
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);
}
}
Questa funzione ha bisogno di due funzioni al di sotto per funzionare. Quindi, basta aggiungerli insieme ad esso.
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'
Questo è quello che ho usato -
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
per 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)
Se non ci sono vincoli di tempo, questo è abbastanza semplice e diretto:
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