Нахождение НОК диапазона чисел
https://stackoverflow.com/questions/185781
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Сегодня я прочитал интересный пост DailyWTF, «Из всех возможных ответов...» и это меня настолько заинтересовало, что я откопал оригинал сообщение на форуме куда оно было подано.Это заставило меня задуматься, как бы я решил эту интересную проблему - исходный вопрос задан на Проект Эйлера как:
2520 - это наименьшее число, которое можно разделить на каждое из чисел от 1 до 10 без каких -либо остатков.
Какое наименьшее число, которое равномерно делится на все числа от 1 до 20?
Чтобы преобразовать это в вопрос программирования, как бы вы создали функцию, которая могла бы найти наименьшее общее кратное для произвольного списка чисел?
У меня невероятно плохо с чистой математикой, несмотря на мой интерес к программированию, но я смог решить эту проблему после небольшого поиска в Google и экспериментов.Мне любопытно, какие еще подходы могут использовать пользователи SO.Если вы так склонны, опубликуйте код ниже, надеюсь, вместе с объяснением.Обратите внимание: хотя я уверен, что библиотеки для вычисления НОД и LCM существуют на разных языках, меня больше интересует что-то, что отображает логику более непосредственно, чем вызов библиотечной функции :-)
Я лучше всего знаком с Python, C, C++ и Perl, но любой язык, который вы предпочитаете, приветствуется.Бонусные баллы за объяснение логики для других людей с математическими проблемами, таких как я.
РЕДАКТИРОВАТЬ:После отправки я нашел похожий вопрос Наименьшее общее кратное для 3 и более чисел но на него ответил тот же базовый код, который я уже разобрался, и реального объяснения нет, поэтому я почувствовал, что это достаточно отличается, чтобы оставить открытым.
Решение
Эта задача интересна тем, что не требует от вас нахождения НОК произвольного набора чисел, вам дан последовательный диапазон.Вы можете использовать вариацию Решето Эратосфена чтобы найти ответ.
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 (< 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 с 10 тысячами итераций по сравнению с методами Джо Биберса и Марка Рэнсомса следующие:
Джос: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)
Однострочник в Хаскеле.
wideLCM = foldl lcm 1
Это то, что я использовал для моей собственной задачи Project Euler 5.
В Хаскеле:
listLCM xs = foldr (lcm) 1 xs
Который вы можете передать список, например:
*Main> listLCM [1..10]
2520
*Main> listLCM [1..2518]
266595767785593803705412270464676976610857635334657316692669925537787454299898002207461915073508683963382517039456477669596355816643394386272505301040799324518447104528530927421506143709593427822789725553843015805207718967822166927846212504932185912903133106741373264004097225277236671818323343067283663297403663465952182060840140577104161874701374415384744438137266768019899449317336711720217025025587401208623105738783129308128750455016347481252967252000274360749033444720740958140380022607152873903454009665680092965785710950056851148623283267844109400949097830399398928766093150813869944897207026562740359330773453263501671059198376156051049807365826551680239328345262351788257964260307551699951892369982392731547941790155541082267235224332660060039217194224518623199770191736740074323689475195782613618695976005218868557150389117325747888623795360149879033894667051583457539872594336939497053549704686823966843769912686273810907202177232140876251886218209049469761186661055766628477277347438364188994340512556761831159033404181677107900519850780882430019800537370374545134183233280000
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.
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;
}
Алгоритм на Хаскеле. Это язык, который я думаю в наше время для алгоритмического мышления. Это может показаться странным, сложным и непривлекательным - добро пожаловать в 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)
Первый шаг - это главные факторы числа. На втором этапе строится хеш-таблица максимального количества раз, которое каждый фактор был замечен, а затем умножается на все вместе.
Это, наверное, самый чистый, самый короткий ответ (с точки зрения строк кода), который я когда-либо видел.
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;
}
Расширяя комментарий @Alexander, я бы отметил, что если вы сможете разложить числа на простые числа, удалить дубликаты, а затем умножить, вы получите ответ.
Например, числа 1-5 имеют простые делители 2,3,2,2,5.Удалите дубликат «2» из списка факторов «4», и вы получите 2,2,3,5.Умножив их, вы получите 60, что и является вашим ответом.
Ссылка на Wolfram, приведенная в предыдущем комментарии, http://mathworld.wolfram.com/LeastCommonMultiple.html использует гораздо более формальный подход, но короткая версия приведена выше.
Ваше здоровье.
