Нахождение LCM диапазона чисел
Сегодня я прочитал интересный пост DailyWTF "Из всех возможных ответов...", и он заинтересовал меня достаточно, чтобы выкопать оригинальное сообщение на форуме, где оно было отправлено. Это заставило меня задуматься о том, как бы я решил эту интересную проблему - первоначальный вопрос поставлен в Project Euler как:
2520 - это наименьшее число, которое можно разделить на каждое из чисел от 1 до 10 без остатка.
Какое наименьшее число делится поровну на все числа от 1 до 20?
Чтобы преобразовать это как вопрос программирования, как бы вы создали функцию, которая может найти наименьшее общее кратное для произвольного списка чисел?
Я невероятно плох с чистой математикой, несмотря на мой интерес к программированию, но я смог решить эту проблему после небольшого поиска в Google и некоторых экспериментов. Мне любопытно, какие другие подходы могут использовать пользователи SO. Если вы так склонны, опубликуйте код ниже, надеюсь, вместе с объяснением. Обратите внимание, что хотя я уверен, что существуют библиотеки для вычисления GCD и LCM на разных языках, меня больше интересует то, что отображает логику более непосредственно, чем вызов библиотечной функции:-)
Я наиболее знаком с Python, C, C++ и Perl, но любой язык, который вы предпочитаете, приветствуется. Бонусные баллы за объяснение логики для других людей с математическими проблемами, таких как я.
РЕДАКТИРОВАТЬ: После отправки я нашел этот похожий вопрос Наименьшее общее множитель для 3 или более чисел, но на него ответил тот же базовый код, который я уже понял, и нет никакого реального объяснения, поэтому я чувствовал, что это было достаточно по-другому, чтобы оставить открытым.
14 ответов
Эта проблема интересна тем, что она не требует от вас найти 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 вы можете увидеть алгоритм на основе сита, особенно оптимизированную версию.
Ответ не требует какой-либо изощренной работы ног с точки зрения факторинга или основных сил и, безусловно, не требует сита Эратосфена.
Вместо этого вы должны рассчитать LCM одной пары, вычислив GCD с использованием алгоритма Евклида (который НЕ требует факторизации, а на самом деле значительно быстрее):
def lcm(a,b):
gcd, tmp = a,b
while tmp != 0:
gcd,tmp = tmp, gcd % tmp
return a*b/gcd
тогда вы можете найти общий LCM my, уменьшая массив, используя вышеупомянутую функцию lcm():
reduce(lcm, range(1,21))
Это быстрое решение, если диапазон от 1 до N.
Ключевое наблюдение заключается в том, что если n (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 с итерациями по 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)
Однострочник в Хаскеле.
wideLCM = foldl lcm 1
Это то, что я использовал для моей собственной задачи Project Euler 5.
В Хаскеле:
listLCM xs = foldr (lcm) 1 xs
Который вы можете передать список, например:
*Main> listLCM [1..10]
2520
*Main> listLCM [1..2518]
266595767785593803705412270464676976610857635334657316692669925537787454299898002207461915073508683963382517039456477669596355816643394386272505301040799324518447104528530927421506143709593427822789725553843015805207718967822166927846212504932185912903133106741373264004097225277236671818323343067283663297403663465952182060840140577104161874701374415384744438137266768019899449317336711720217025025587401208623105738783129308128750455016347481252967252000274360749033444720740958140380022607152873903454009665680092965785710950056851148623283267844109400949097830399398928766093150813869944897207026562740359330773453263501671059198376156051049807365826551680239328345262351788257964260307551699951892369982392731547941790155541082267235224332660060039217194224518623199770191736740074323689475195782613618695976005218868557150389117325747888623795360149879033894667051583457539872594336939497053549704686823966843769912686273810907202177232140876251886218209049469761186661055766628477277347438364188994340512556761831159033404181677107900519850780882430019800537370374545134183233280000
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;
}
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.
Алгоритм на Хаскеле. Это язык, на котором я думаю в настоящее время для алгоритмического мышления. Это может показаться странным, сложным и непривлекательным - добро пожаловать в 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
Это, наверное, самый чистый, самый короткий ответ (с точки зрения строк кода), который я когда-либо видел.
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
Вот мой удар по 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)
Шаг первый получает главные факторы числа. На втором этапе строится хеш-таблица максимального количества раз, которое каждый фактор был замечен, а затем умножается на все вместе.
Вот мое решение 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;
}
Вот мой ответ в 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]);
Расширяя комментарий @Alexander, я хотел бы отметить, что если вы можете скомпоновать числа с их простыми числами, удалить дубликаты, а затем перемножить, у вас будет свой ответ.
Например, 1-5 имеют главные факторы 2,3,2,2,5. Удалите дублированный "2" из списка факторов "4", и у вас есть 2,2,3,5. Умножение их вместе дает 60, что является вашим ответом.
Ссылка на Wolfram, предоставленная в предыдущем комментарии, http://mathworld.wolfram.com/LeastCommonMultiple.html использует гораздо более формальный подход, но краткая версия приведена выше.
Приветствия.