StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This problem is interesting because it doesn't require you to find the LCM of an arbitrary set of numbers, you're given a consecutive range. You can use a variation of the <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer">Sieve of Eratosthenes</a> to find the answer.</p> <pre><code>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) </code></pre> <p><hr> Edit: A recent upvote made me re-examine this answer which is over 3 years old. My first observation is that I would have written it a little differently today, using <code>enumerate</code> for example.</p> <p>The second observation is that this algorithm only works if the start of the range is 2 or less, because it doesn't try to sieve out the common factors below the start of the range. For example, RangeLCM(10, 12) returns 1320 instead of the correct 660.</p> <p>The third observation is that nobody attempted to time this answer against any other answers. My gut said that this would improve over a brute force LCM solution as the range got larger. Testing proved my gut correct, at least this once.</p> <p>Since the algorithm doesn't work for arbitrary ranges, I rewrote it to assume that the range starts at 1. I removed the call to <code>reduce</code> at the end, as it was easier to compute the result as the factors were generated. I believe the new version of the function is both more correct and easier to understand.</p> <pre><code>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 </code></pre> <p>Here are some timing comparisons against the original and the solution proposed by <a href="https://stackoverflow.com/a/196472/5987">Joe Bebel</a> which is called <code>RangeEuclid</code> in my tests.</p> <pre><code>>>> 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 </code></pre> <p>For the range of 1 to 20 given in the question, Euclid's algorithm beats out both my old and new answers. For the range of 1 to 100 you can see the sieve-based algorithm pull ahead, especially the optimized version.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload