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

Расширяя комментарий @Alexander, я хотел бы указать, что если вы можете разложить числа на их простые числа, удалить дубликаты, а затем умножить, вы получите свой ответ.

Например, 1-5 имеют простые делители 2,3,2,2,5. Удалите дублирующуюся цифру «2» из списка факторов «4», и у вас будет 2,2,3,5. Их умножение дает 60, и это ваш ответ.

Ссылка на Wolfram, представленная в предыдущем комментарии, http://mathworld.wolfram.com/LeastCommonMultiple.html, представляет собой гораздо более формальный подход, но краткая версия приведена выше.

Ваше здоровье.

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

Скажем, 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. Итак, НОК: 264600 = 2 ^ 3 * 3 ^ 3 * 5 ^ 2 * 7 ^ 2.

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

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)

Второе наблюдение: этот алгоритм работает, только если начало диапазона равно 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 вы можете увидеть, что алгоритм на основе сита вытягивается вперед, особенно оптимизированная версия.

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

Вот мой Python-удар:

#!/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)

На первом этапе вычисляются простые множители числа. На втором этапе создается хеш-таблица максимального количества просмотров каждого фактора, а затем все они умножаются.

Однострочный текст в Haskell.

wideLCM = foldl lcm 1

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

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

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

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

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

Для этого есть быстрое решение, если диапазон составляет от 1 до N.

Ключевое наблюдение состоит в том, что если 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).

Обновлено:

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

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

Джоуз: 1,85 секунды Оценки: 3.26с Моя: 0,33 с

Вот график журнала с результатами до 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)

В Haskell:

listLCM xs =  foldr (lcm) 1 xs

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

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

Это, вероятно, самый чистый и кратчайший ответ (как с точки зрения строк кода), который я видел до сих пор.

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)

источник: http://www.s-anand.net/euler.html

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

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

//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]);

Вот мое решение для 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;
}

Вот решение с использованием 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;
}