Suche nach der LCM einer Reihe von Zahlen

Question

Ich las eine interessante DailyWTF Post heute, "Out of All The Possible Answers..." und es interessierte mich genug, um das Original forum post wo es eingereicht wurde auszugraben. Dies hat ich denken, wie ich dieses interessantes Problem lösen würde - die ursprüngliche Frage auf Project Euler als gestellt wird:

2520 ist die kleinste Zahl, die von jedem der Zahlen von 1 bis 10 ohne Rest teilbar ist.

Was ist die kleinste Zahl, die durch die Zahlen von 1 bis 20 gleichmäßig teilbar ist?

Um dies als eine Programmierung Frage zu reformieren, wie würden Sie eine Funktion erstellen, die die kleinste gemeinsame Vielfache für eine beliebige Liste von Zahlen finden können?

Ich bin unglaublich schlecht mit reinem Mathe, trotz meines Interesses an der Programmierung, aber ich konnte das nach ein wenig Googeln und etwas Experimentieren lösen. Ich bin gespannt, welche anderen Ansätze SO-Nutzer annehmen könnten. Wenn Sie so geneigt sind, posten Sie etwas Code unten, hoffentlich zusammen mit einer Erklärung. Beachten Sie, dass, während ich bin sicher, Bibliotheken existieren, um die GCD und LCM in verschiedenen Sprachen zu berechnen, interessiere ich mich mehr für etwas, das die Logik direkter als eine Bibliotheksfunktion aufrufen :-)

Ich bin am vertrautesten mit Python, C, C++ und Perl, aber jede Sprache, die Sie bevorzugen, ist willkommen. Bonuspunkte für die Erklärung der Logik für andere Mathematiker wie mich.

EDIT: Nach dem Absenden ich diese ähnliche Frage Least common multiple for 3 or more numbers finden tat, aber es wurde mit dem gleichen grundlegenden Code, den ich bereits herausgefunden und es gibt keine wirkliche Erklärung beantwortet, so fühlte ich dies anders genug offen zu lassen war.

Answer 1

Dieses Problem ist interessant, weil es nicht erforderlich ist, dass Sie die LCM einer beliebigen Menge von Zahlen finden, Sie erhalten einen fortlaufenden Bereich. Sie können eine Variation des Sieve of Eratosthenes verwenden, um die Antwort zu finden.

def RangeLCM(first, last): 
    factors = range(first, last+1) 
    for i in range(0, len(factors)): 
     if factors[i] != 1: 
      n = first + i 
      for j in range(2*n, last+1, n): 
       factors[j-first] = factors[j-first]/factors[i] 
    return reduce(lambda a,b: a*b, factors, 1) 

---

Edit: Eine kürzlich upvote hat mich diese Antwort erneut zu prüfen, die mehr als 3 Jahre alt ist. Meine erste Beobachtung ist, dass ich es heute etwas anders geschrieben hätte, zum Beispiel mit enumerate.

Die zweite Beobachtung ist, dass dieser Algorithmus nur funktioniert, wenn der Anfang des Bereichs 2 oder weniger ist, weil es nicht versucht, die gemeinsamen Faktoren unter dem Anfang des Bereichs auszusortieren. Zum Beispiel gibt RangeLCM (10, 12) 1320 statt der korrekten 660 zurück.

Die dritte Beobachtung ist, dass niemand versucht hat, diese Antwort mit anderen Antworten zu synchronisieren. Mein Bauchgefühl sagte, dass sich dies gegenüber einer Brute-Force-LCM-Lösung verbessern würde, wenn die Reichweite größer würde. Das Testen hat bewiesen, dass mein Darm korrekt ist, zumindest dieses Mal.

Da der Algorithmus nicht für beliebige Bereiche funktioniert, habe ich ihn umgeschrieben, um anzunehmen, dass der Bereich bei 1 beginnt. Ich entfernte den Aufruf am Ende zu reduce, da es einfacher war, das Ergebnis zu berechnen, wie die Faktoren generiert wurden . Ich glaube, dass die neue Version der Funktion sowohl korrekter als auch einfacher zu verstehen ist.

def RangeLCM2(last): 
    factors = range(last+1) 
    result = 1 
    for n in range(last+1): 
     if factors[n] > 1: 
      result *= factors[n] 
      for j in range(2*n, last+1, n): 
       factors[j] /= factors[n] 
    return result 

Hier sind einige Timing-Vergleiche gegen die ursprüngliche und die Lösung von Joe Bebel vorgeschlagen, die RangeEuclid in meinen Tests genannt wird.

>>> t=timeit.timeit 
>>> t('RangeLCM.RangeLCM(1, 20)', 'import RangeLCM') 
17.999292996735676 
>>> t('RangeLCM.RangeEuclid(1, 20)', 'import RangeLCM') 
11.199833288867922 
>>> t('RangeLCM.RangeLCM2(20)', 'import RangeLCM') 
14.256165588084514 
>>> t('RangeLCM.RangeLCM(1, 100)', 'import RangeLCM') 
93.34979585394194 
>>> t('RangeLCM.RangeEuclid(1, 100)', 'import RangeLCM') 
109.25695507389901 
>>> t('RangeLCM.RangeLCM2(100)', 'import RangeLCM') 
66.09684505991709 

Für den Bereich von 1 bis 20 in der Frage gegeben, schlägt Euklids Algorithmus beid Antworten meiner alte und neue aus. Für den Bereich von 1 bis 100 sehen Sie den siebbasierten Algorithmus, insbesondere die optimierte Version.

Answer 2

In Erweiterung auf @ Alexanders Kommentar, würde ich darauf hinweisen, dass, wenn Sie die Zahlen zu ihren Primzahlen Faktor, entfernen Duplikate, dann multiplizieren-out, Sie werden Ihre Antwort haben.

Zum Beispiel haben 1-5 die Primfaktoren 2,3,2,2,5. Entferne die doppelte '2' von der Faktorliste der '4' und du hast 2,2,3,5. Multipliziert man diese zusammen ergibt das 60, was deine Antwort ist.

Der Wolfram-Link im vorherigen Kommentar, http://mathworld.wolfram.com/LeastCommonMultiple.html geht in einen viel formelleren Ansatz, aber die kurze Version ist oben.

Prost.

Answer 3

Die LCM von einer oder mehreren Zahlen ist das Produkt aller verschiedenen Primfaktoren in allen Zahlen, jede Primzahl zur Potenz des Maximums aller Potenzen, zu denen diese Primzahl in den Zahlen erscheint, die man nimmt das LCM von.

Sagen Sie 900 = 2^3 * 3^2 * 5^2, 26460 = 2^2 * 3^3 * 5^1 * 7^2. Die maximale Leistung von 2 ist 3, die maximale Leistung von 3 ist 3, die maximale Leistung von 5 ist 1, die maximale Leistung von 7 ist 2 und die maximale Leistung von einem höheren Prime ist 0. So ist das LCM: 264600 = 2^3 * 3^3 * 5^2 * 7^2.

Answer 4

Ein Algorithmus in Haskell. Das ist die Sprache, in die ich heutzutage für das algorithmische Denken denke. Das mag seltsam, kompliziert und wenig einladend erscheinen - willkommen in Haskell!

primes :: (Integral a) => [a] 
--implementation of primes is to be left for another day. 

primeFactors :: (Integral a) => a -> [a] 
primeFactors n = go n primes where 
    go n ps@(p : pt) = 
     if q < 1 then [] else 
     if r == 0 then p : go q ps else 
     go n pt 
     where (q, r) = quotRem n p 

multiFactors :: (Integral a) => a -> [(a, Int)] 
multiFactors n = [ (head xs, length xs) | xs <- group $ primeFactors $ n ] 

multiProduct :: (Integral a) => [(a, Int)] -> a 
multiProduct xs = product $ map (uncurry (^)) $ xs 

mergeFactorsPairwise [] bs = bs 
mergeFactorsPairwise as [] = as 
mergeFactorsPairwise a@((an, am) : _) b@((bn, bm) : _) = 
    case compare an bn of 
     LT -> (head a) : mergeFactorsPairwise (tail a) b 
     GT -> (head b) : mergeFactorsPairwise a (tail b) 
     EQ -> (an, max am bm) : mergeFactorsPairwise (tail a) (tail b) 

wideLCM :: (Integral a) => [a] -> a 
wideLCM nums = multiProduct $ foldl mergeFactorsPairwise [] $ map multiFactors $ nums 

Answer 5

Hier ist mein Python Stich an es:

#!/usr/bin/env python 

from operator import mul 

def factor(n): 
    factors = {} 
    i = 2 
    while i <= n and n != 1: 
     while n % i == 0: 
      try: 
       factors[i] += 1 
      except KeyError: 
       factors[i] = 1 
      n = n/i 
     i += 1 
    return factors 

base = {} 
for i in range(2, 2000): 
    for f, n in factor(i).items(): 
     try: 
      base[f] = max(base[f], n) 
     except KeyError: 
      base[f] = n 

print reduce(mul, [f**n for f, n in base.items()], 1) 

Schritt eins die Primfaktoren einer Reihe bekommt. Im zweiten Schritt wird eine Hash-Tabelle erstellt, in der die maximale Anzahl der einzelnen Faktoren angezeigt wird. Anschließend werden sie alle miteinander multipliziert.

Answer 6

Einliner in Haskell.

wideLCM = foldl lcm 1 

Dies ist, was ich für mein eigenes Projekt Euler Problem 5.

Answer 7

Die Antwort erfordert nicht überhaupt in Bezug auf Factoring oder Primzahlpotenzen jede Beinarbeit verwendet, und ganz sicher erfordert nicht die Sieve von Eratosthenes.

Stattdessen sollten Sie die LCM eines einzigen Paares berechnen, indem der GCD Berechnung Euklid-Algorithmus (nicht Faktorisierung erfordert, und in der Tat ist deutlich schneller):

def lcm(a,b): 
    gcd, tmp = a,b 
    while tmp != 0: 
     gcd,tmp = tmp, gcd % tmp 
    return a*b/gcd 

dann können Sie die Gesamt finden LCM meint das Array unter Verwendung des oben LCM reduziert() Funktion:

reduce(lcm, range(1,21)) 

Answer 8

print "LCM of 4 and 5 = ".LCM(4,5)."\n"; 

sub LCM { 
    my ($a,$b) = @_;  
    my ($af,$bf) = (1,1); # The factors to apply to a & b 

    # Loop and increase until A times its factor equals B times its factor 
    while ($a*$af != $b*$bf) { 
     if ($a*$af>$b*$bf) {$bf++} else {$af++}; 
    } 
    return $a*$af; 
} 

Answer 9

Es ist eine schnelle Lösung für dieses Problem, solange der Bereich 1 bis N ist

Die Schlüsselbeobachtung ist, dass wenn n (< N) p_1^a_1 * p_2^a_2 * ... p_k * a_k Primfaktorzerlegung hat, dann wird es dazu beitragen, genau die gleichen Faktoren, die LCM als p_1^a_1 und p_2^a_2 ... p_k^a_k. Und jede dieser Kräfte liegt ebenfalls im Bereich von 1 bis N. Wir brauchen also nur die höchsten reinen Primzahlpotenzen kleiner als N. 20

Zum Beispiel haben zu prüfen, wir

2^4 = 16 < 20 
3^2 = 9 < 20 
5^1 = 5 < 20 
7 
11 
13 
17 
19 

alle diese Primzahlpotenzen Multipliziert man zusammen wir das gewünschte Ergebnis von

2*2*2*2*3*3*5*7*11*13*17*19 = 232792560 

erhalten

So in Pseudo-Code:

def lcm_upto(N): 
    total = 1; 
    foreach p in primes_less_than(N): 
    x=1; 
    while x*p <= N: 
     x=x*p; 
    total = total * x 
    return total 

Jetzt können Sie die innere Schleife zwicken wo rk etwas anders, um mehr Geschwindigkeit zu erhalten, und Sie können die primes_less_than(N) Funktion vorberechnen.

EDIT:

Aufgrund einer kürzlich upvote ich decideded dies nochmals zu besuchen, um zu sehen, wie die Geschwindigkeit Vergleich mit den anderen aufgeführten Algorithmen ging.

-Timing für Bereich 1-160 mit 10k Iterationen gegen Joe Beibers und Mark Ransoms Methoden sind wie folgt:

Joes: 1.85s Marks: 3.26s Mine: 0.33s

Hier ist ein Protokoll -log Diagramm mit den Ergebnissen bis zu 300.

-Code für mein Test finden Sie hier:

import timeit 


def RangeLCM2(last): 
    factors = range(last+1) 
    result = 1 
    for n in range(last+1): 
     if factors[n] > 1: 
      result *= factors[n] 
      for j in range(2*n, last+1, n): 
       factors[j] /= factors[n] 
    return result 


def lcm(a,b): 
    gcd, tmp = a,b 
    while tmp != 0: 
     gcd,tmp = tmp, gcd % tmp 
    return a*b/gcd 

def EuclidLCM(last): 
    return reduce(lcm,range(1,last+1)) 

primes = [ 
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 
179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 
233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 
419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 
467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 
547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 
607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 
661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 
739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 
811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 
877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 
947, 953, 967, 971, 977, 983, 991, 997 ] 

def FastRangeLCM(last): 
    total = 1 
    for p in primes: 
     if p>last: 
      break 
     x = 1 
     while x*p <= last: 
      x = x * p 
     total = total * x 
    return total 


print RangeLCM2(20) 
print EculidLCM(20) 
print FastRangeLCM(20) 

print timeit.Timer('RangeLCM2(20)', "from __main__ import RangeLCM2").timeit(number=10000) 
print timeit.Timer('EuclidLCM(20)', "from __main__ import EuclidLCM").timeit(number=10000) 
print timeit.Timer('FastRangeLCM(20)', "from __main__ import FastRangeLCM").timeit(number=10000) 

print timeit.Timer('RangeLCM2(40)', "from __main__ import RangeLCM2").timeit(number=10000) 
print timeit.Timer('EuclidLCM(40)', "from __main__ import EuclidLCM").timeit(number=10000) 
print timeit.Timer('FastRangeLCM(40)', "from __main__ import FastRangeLCM").timeit(number=10000) 

print timeit.Timer('RangeLCM2(60)', "from __main__ import RangeLCM2").timeit(number=10000) 
print timeit.Timer('EuclidLCM(60)', "from __main__ import EuclidLCM").timeit(number=10000) 
print timeit.Timer('FastRangeLCM(60)', "from __main__ import FastRangeLCM").timeit(number=10000) 

print timeit.Timer('RangeLCM2(80)', "from __main__ import RangeLCM2").timeit(number=10000) 
print timeit.Timer('EuclidLCM(80)', "from __main__ import EuclidLCM").timeit(number=10000) 
print timeit.Timer('FastRangeLCM(80)', "from __main__ import FastRangeLCM").timeit(number=10000) 

print timeit.Timer('RangeLCM2(100)', "from __main__ import RangeLCM2").timeit(number=10000) 
print timeit.Timer('EuclidLCM(100)', "from __main__ import EuclidLCM").timeit(number=10000) 
print timeit.Timer('FastRangeLCM(100)', "from __main__ import FastRangeLCM").timeit(number=10000) 

print timeit.Timer('RangeLCM2(120)', "from __main__ import RangeLCM2").timeit(number=10000) 
print timeit.Timer('EuclidLCM(120)', "from __main__ import EuclidLCM").timeit(number=10000) 
print timeit.Timer('FastRangeLCM(120)', "from __main__ import FastRangeLCM").timeit(number=10000) 

print timeit.Timer('RangeLCM2(140)', "from __main__ import RangeLCM2").timeit(number=10000) 
print timeit.Timer('EuclidLCM(140)', "from __main__ import EuclidLCM").timeit(number=10000) 
print timeit.Timer('FastRangeLCM(140)', "from __main__ import FastRangeLCM").timeit(number=10000) 

print timeit.Timer('RangeLCM2(160)', "from __main__ import RangeLCM2").timeit(number=10000) 
print timeit.Timer('EuclidLCM(160)', "from __main__ import EuclidLCM").timeit(number=10000) 
print timeit.Timer('FastRangeLCM(160)', "from __main__ import FastRangeLCM").timeit(number=10000) 

Answer 10

In Haskell:

listLCM xs = foldr (lcm) 1 xs 

denen Sie eine Liste zum Beispiel passieren können:

*Main> listLCM [1..10] 
2520 
*Main> listLCM [1..2518] 
266595767785593803705412270464676976610857635334657316692669925537787454299898002207461915073508683963382517039456477669596355816643394386272505301040799324518447104528530927421506143709593427822789725553843015805207718967822166927846212504932185912903133106741373264004097225277236671818323343067283663297403663465952182060840140577104161874701374415384744438137266768019899449317336711720217025025587401208623105738783129308128750455016347481252967252000274360749033444720740958140380022607152873903454009665680092965785710950056851148623283267844109400949097830399398928766093150813869944897207026562740359330773453263501671059198376156051049807365826551680239328345262351788257964260307551699951892369982392731547941790155541082267235224332660060039217194224518623199770191736740074323689475195782613618695976005218868557150389117325747888623795360149879033894667051583457539872594336939497053549704686823966843769912686273810907202177232140876251886218209049469761186661055766628477277347438364188994340512556761831159033404181677107900519850780882430019800537370374545134183233280000 

Answer 11

Dies ist wahrscheinlich die sauberste, kürzeste Antwort (sowohl in Bezug auf Codezeilen), die ich Ich habe es bisher gesehen.

def gcd(a,b): return b and gcd(b, a % b) or a 
def lcm(a,b): return a * b/gcd(a,b) 

n = 1 
for i in xrange(1, 21): 
    n = lcm(n, i) 

Quelle: http://www.s-anand.net/euler.html

Answer 12

Hier ist meine Antwort in JavaScript. Ich habe mich zum ersten Mal mit Primzahlen befasst und eine nützliche Funktion von wiederverwendbarem Code entwickelt, um Primzahlen zu finden und auch Primfaktoren zu finden, aber am Ende entschied ich, dass dieser Ansatz einfacher war.

Es gibt nichts Einzigartiges in meiner Antwort, das oben nicht gepostet wurde, es ist nur in Javascript, das ich nicht speziell sah.

//least common multipe of a range of numbers 
function smallestCommons(arr) { 
    arr = arr.sort(); 
    var scm = 1; 
    for (var i = arr[0]; i<=arr[1]; i+=1) { 
     scm = scd(scm, i); 
    } 
    return scm; 
} 


//smallest common denominator of two numbers (scd) 
function scd (a,b) { 
    return a*b/gcd(a,b); 
} 


//greatest common denominator of two numbers (gcd) 
function gcd(a, b) { 
    if (b === 0) { 
     return a; 
    } else { 
     return gcd(b, a%b); 
    } 
}  

smallestCommons([1,20]); 

Answer 13

Hier ist meine Javascript-Lösung, ich hoffe, Sie finden es einfach zu folgen:

function smallestCommons(arr) { 
    var min = Math.min(arr[0], arr[1]); 
    var max = Math.max(arr[0], arr[1]); 

    var smallestCommon = min * max; 

    var doneCalc = 0; 

    while (doneCalc === 0) { 
    for (var i = min; i <= max; i++) { 
     if (smallestCommon % i !== 0) { 
     smallestCommon += max; 
     doneCalc = 0; 
     break; 
     } 
     else { 
     doneCalc = 1; 
     } 
    } 
    } 

    return smallestCommon; 
}