Нахождение LCM диапазона чисел

Question

Сегодня я прочитал интересный пост DailyWTF, "Из всех возможных ответов ..." , и он заинтересовал меня достаточно, чтобы выкопать оригинальное сообщение на форуме , где оно было отправлено. , Это заставило меня задуматься о том, как бы я решил эту интересную проблему - оригинальный вопрос поставлен на Project Euler как:

2520 - наименьшее число, которое можно разделить на каждое из числа от 1 до 10 без остатка.

Какое наименьшее число делится на все цифры от 1 до 20?

Чтобы преобразовать это как вопрос программирования, как бы вы создали функцию, которая может найти наименьшее общее кратное для произвольного списка чисел?

Я невероятно плох с чистой математикой, несмотря на мой интерес к программированию, но я смог решить эту проблему после небольшого поиска в Google и некоторых экспериментов. Мне любопытно, какие другие подходы могут использовать пользователи SO. Если вы так склонны, опубликуйте код ниже, надеюсь, вместе с объяснением. Обратите внимание, что хотя я уверен, что существуют библиотеки для вычисления GCD и LCM на разных языках, меня больше интересует то, что отображает логику более непосредственно, чем вызов библиотечной функции :-)

Я больше всего знаком с Python, C, C ++ и Perl, но любой язык, который вы предпочитаете, приветствуется. Бонусные баллы за объяснение логики для других людей с математическими проблемами, таких как я.

РЕДАКТИРОВАТЬ : После отправки я нашел этот похожий вопрос Наименьшее общее множитель для 3 или более чисел , но на него ответил тот же базовый код, который я уже понял, и нет реального объяснение, поэтому я чувствовал, что это было достаточно по-другому, чтобы оставить открытым.

Answer 1

Ответ не требует какой-либо изощренной работы ног с точки зрения факторинга или основных сил и, безусловно, не требует сита Эратосфена.

Вместо этого вы должны рассчитать LCM для одной пары, вычислив GCD с использованием алгоритма Евклида (который НЕ требует факторизации и фактически значительно быстрее):

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

тогда вы можете найти общий LCM мой уменьшающий массив, используя вышеупомянутую функцию lcm ():

reduce(lcm, range(1,21))

Answer 2

Эта проблема интересна, потому что она не требует от вас найти LCM произвольного набора чисел, вы получаете последовательный диапазон. Вы можете использовать вариант Сито Эратосфена , чтобы найти ответ.

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)

---

Редактировать: недавнее возрождение заставило меня пересмотреть этот ответ, который старше 3 лет. Мое первое наблюдение состоит в том, что я написал бы это немного по-другому, используя, например, enumerate. Чтобы сделать его совместимым с Python 3, потребовалось несколько небольших изменений.

Второе наблюдение состоит в том, что этот алгоритм работает, только если начало диапазона составляет 2 или меньше, потому что он не пытается просеять общие факторы ниже начала диапазона. Например, RangeLCM (10, 12) возвращает 1320 вместо правильных 660.

Третье замечание: никто не пытался сравнить этот ответ с любыми другими ответами. Моя интуиция сказала, что это улучшится по сравнению с решением для грубой силы LCM, когда диапазон увеличится. Тестирование подтвердило мою интуицию, по крайней мере, один раз.

Поскольку алгоритм не работает для произвольных диапазонов, я переписал его, предполагая, что диапазон начинается с 1. Я удалил вызов на reduce в конце, так как было легче вычислить результат, так как факторы были генерироваться. Я считаю, что новая версия функции является более правильной и понятной.

def RangeLCM2(last):
    factors = list(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

Вот некоторые временные сравнения с оригиналом и решением, предложенным Джо Бебелем , который в моих тестах называется RangeEuclid.

>>> 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

Для диапазона от 1 до 20, указанного в вопросе, алгоритм Евклида выбивает как мои старые, так и новые ответы. Для диапазона от 1 до 100 вы можете увидеть алгоритм на основе сита, особенно оптимизированную версию.

Answer 3

Это быстрое решение, если диапазон от 1 до N.

Ключевое наблюдение состоит в том, что если n (p_1^a_1 * p_2^a_2 * ... p_k * a_k, тогда он будет вносить в LCM точно такие же факторы, как p_1^a_1 и p_2^a_2, ... p_k^a_k. И каждая из этих степеней также находится в диапазоне от 1 до N. Таким образом, нам нужно только рассмотреть высшие чистые простые степени меньше, чем N.

Например, для 20 у нас есть

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

Умножая все эти основные силы вместе, мы получаем требуемый результат

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

Так в псевдокоде:

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

Теперь вы можете настроить внутренний цикл так, чтобы он работал немного по-другому, чтобы получить большую скорость, и вы можете предварительно рассчитать функцию primes_less_than(N).

EDIT:

Из-за недавнего повышения я решил вернуться к этому, чтобы увидеть, как пошло сравнение скорости с другими перечисленными алгоритмами.

Сроки для диапазона 1-160 с итерациями по 10 тыс. Против методов Джо Бейберса и Марка Рэнсомса:

Джо: 1,85 с Оценка: 3.26 с Шахта: 0,33 с

Вот график log-log с результатами до 300.

Код для моего теста можно найти здесь:

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 4

Однострочник в Хаскеле.

wideLCM = foldl lcm 1

Это то, что я использовал для моей собственной задачи Project Euler 5.

Answer 5

В Хаскеле:

listLCM xs =  foldr (lcm) 1 xs

Какой вы можете передать список, например:

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

Answer 6

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 7

LCM одного или нескольких чисел - это произведение всех различных простых множителей во всех числах, каждое простое число на степень максимума всех степеней, к которым это простое число появляется в числах, которые принимает LCM.

Скажите 900 = 2 ^ 3 * 3 ^ 2 * 5 ^ 2, 26460 = 2 ^ 2 * 3 ^ 3 * 5 ^ 1 * 7 ^ 2. Максимальная мощность 2 равна 3, максимальная мощность 3 равна 3, максимальная мощность 5 равна 1, максимальная мощность 7 равна 2, а максимальная мощность любого более высокого простого числа равна 0. Таким образом, LCM: 264600 = 2 ^ 3 * 3 ^ 3 * 5 ^ 2 * 7 ^ 2.

Answer 8

Алгоритм на Хаскеле. Это язык, который я думаю в наше время для алгоритмического мышления. Это может показаться странным, сложным и непривлекательным - добро пожаловать в 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 9

Вот решение с использованием C Lang

#include<stdio.h>
    int main(){
    int a,b,lcm=1,small,gcd=1,done=0,i,j,large=1,div=0;
    printf("Enter range\n");
    printf("From:");
    scanf("%d",&a);
    printf("To:");
    scanf("%d",&b);
    int n=b-a+1;
    int num[30];
    for(i=0;i<n;i++){
        num[i]=a+i;
    }
    //Finds LCM
    while(!done){
        for(i=0;i<n;i++){
            if(num[i]==1){
                done=1;continue;
            }
            done=0;
            break;
        }
        if(done){
            continue;
        }
        done=0;
        large=1;
        for(i=0;i<n;i++){
            if(num[i]>large){
                large=num[i];
            }
        }
        div=0;
        for(i=2;i<=large;i++){
            for(j=0;j<n;j++){
                if(num[j]%i==0){
                    num[j]/=i;div=1;
                }
                continue;
            }
            if(div){
                lcm*=i;div=0;break;
            }
        }
    }
    done=0;
    //Finds GCD
    while(!done){
        small=num[0];
        for(i=0;i<n;i++){
            if(num[i]<small){
                small=num[i];
            }
        }
        div=0;
        for(i=2;i<=small;i++){
            for(j=0;j<n;j++){
                if(num[j]%i==0){
                    div=1;continue;
                }
                div=0;break;
            }
            if(div){
                for(j=0;j<n;j++){
                    num[j]/=i;
                }
                gcd*=i;div=0;break;
            }
        }
        if(i==small+1){
            done=1;
        }
    }
    printf("LCM = %d\n",lcm);
    printf("GCD = %d\n",gcd);
    return 0;
}

Answer 10

Вот мое решение javascript, надеюсь, вам будет легко следовать:

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;
}