다양한 숫자의 LCM 찾기
https://stackoverflow.com/questions/185781
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
오늘은 흥미로운 DailyWTF 게시물을 읽었습니다. "가능한 모든 답변에서 ..." 그리고 그것은 원본을 파헤칠만큼 충분히 관심이 있습니다 포럼 게시물 제출 된 곳. 이것은 내가이 흥미로운 문제를 어떻게 해결할 것인지 생각하게 만들었습니다. 원래의 질문은 프로젝트 오일러 처럼:
2520은 나머지없이 각 숫자로 1에서 10으로 나눌 수있는 가장 작은 숫자입니다.
1에서 20까지의 모든 숫자로 균등하게 나눌 수있는 가장 작은 숫자는 무엇입니까?
이것을 프로그래밍 질문으로 개혁하기 위해 임의의 숫자 목록에 대해 가장 일반적인 배수를 찾을 수있는 함수를 어떻게 작성 하시겠습니까?
나는 프로그래밍에 대한 관심에도 불구하고 순수한 수학으로 엄청나게 나쁘지만 약간의 인터넷 검색과 약간의 실험 후에 이것을 해결할 수있었습니다. 사용자가 무엇을 취할 수 있는지 궁금합니다. 당신이 너무 기울어지면, 설명과 함께 아래 코드를 게시하십시오. GCD와 LCM을 다양한 언어로 계산하기 위해 라이브러리가 존재한다고 확신하지만, 라이브러리 기능을 호출하는 것보다 논리를 더 직접 표시하는 것에 더 관심이 있습니다 .-).
Python, C, C ++ 및 Perl에 가장 익숙하지만 선호하는 언어는 환영합니다. 다른 수학적으로 도전받은 사람들의 논리를 설명하기위한 보너스 포인트.
편집하다: 제출 한 후 나는 이와 비슷한 질문을 찾았습니다 3 개 이상의 숫자에 대해 가장 일반적인 배수 그러나 그것은 내가 이미 알아 낸 것과 동일한 기본 코드로 답변되었고 실제 설명이 없기 때문에 이것이 열려있을 정도로 다른 것이라고 생각했습니다.
해결책
이 문제는 임의의 숫자 세트의 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)은 올바른 660 대신 1320을 반환합니다.
세 번째 관찰은 아무도 다른 답변에 대해이 답변을 시간에 타지 않았다는 것입니다. 내 직감은 범위가 커짐에 따라 이것이 무차별 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 범위의 경우 Sieve 기반 알고리즘이 앞서 나가는 것을 볼 수 있습니다. 특히 최적화 된 버전.
다른 팁
대답은 팩토링 또는 주요 힘의 관점에서 전혀 멋진 발판을 요구하지 않으며, 가장 확실히 Eratosthenes의 체를 요구하지는 않습니다.
대신, EUCLID의 알고리즘을 사용하여 GCD를 계산하여 단일 쌍의 LCM을 계산해야합니다 (요인화가 필요하지 않으며 실제로는 훨씬 빠릅니다).
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))
범위가 1에서 N에서 N이면 이에 대한 빠른 해결책이 있습니다.
주요 관찰은 IF입니다 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) 기능.
편집하다:
최근의 upvote로 인해 나는 이것을 다시 방문하기로 결정했습니다. 다른 나열된 알고리즘과의 속도 비교가 어떻게 진행되었는지 확인했습니다.
Joe Beibers 및 Mark Ransoms 방법에 대한 10K 반복의 1-160 범위 타이밍은 다음과 같습니다.
Joes : 1.85s 마크 : 3.26S 광산 : 0.33s
다음은 최대 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의 한 라이너.
wideLCM = foldl lcm 1
이것이 제가 자신의 프로젝트 Euler 문제 5에 사용한 것입니다.
Haskell에서 :
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라고 말합니다. 최대 전력은 3, 3의 최대 전력은 3, 5의 최대 전력은 1이고, 최대 전력은 7이고, 가장 높은 프라임의 최대 전력은 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의 알고리즘. 이것은 요즘 알고리즘 사고에 대해 내가 생각하는 언어입니다. 이것은 이상하고 복잡하며 초대되지 않은 것처럼 보일 수 있습니다. 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
내 파이썬 찌르기는 다음과 같습니다.
#!/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)
1 단계는 숫자의 주요 요인을 얻습니다. 2 단계는 각 요인이 보이는 최대 횟수의 해시 테이블을 구축 한 다음 모두 함께 곱합니다.
이것은 아마도 내가 지금까지 본 가장 깨끗하고 가장 짧은 답변 (코드 라인 측면에서) 일 것입니다.
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)
JavaScript의 내 대답은 다음과 같습니다. 나는 먼저 Primes에서 이것에 접근했고, 재사용 가능한 코드의 좋은 기능을 개발하고 프라임을 찾고 주요 요인을 찾기 위해이 접근법이 더 간단하다고 결정했습니다.
내 대답에는 위에 게시되지 않은 독특한 것이 없으며, 제가 보지 못한 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입니다. '4'의 요인 목록에서 복제 된 '2'를 제거하면 2,2,3,5가 있습니다. 함께 그 사람들을 곱하면 60이 있습니다. 이것이 당신의 대답입니다.
이전 의견에 제공된 Wolfram 링크, http://mathworld.wolfram.com/leastcommonmultiple.html 훨씬 더 공식적인 접근 방식에 들어가지만 짧은 버전은 위에 있습니다.
건배.
