इस के लिए एक तेजी से समाधान है, जब तक कि सीमा एन
करने के लिए 1 है
कुंजी अवलोकन है कि अगर n (< एन) प्रधानमंत्री गुणन p_1^a_1 * p_2^a_2 * ... p_k * a_k, है तो यह बिल्कुल वैसा ही कारकों एलसीएम को p_1^a_1 और p_2^a_2 ... p_k^a_k के रूप में योगदान करेगा। और इनमें से प्रत्येक शक्ति 1 से एन सीमा में भी है। इस प्रकार हम केवल हम
2^4 = 16 < 20
3^2 = 9 < 20
5^1 = 5 < 20
7
11
13
17
19
इन सभी प्रमुख शक्तियों को एक साथ जोड़ हम के लिए आवश्यक परिणाम प्राप्त है 20 के लिए एन से उच्चतम शुद्ध प्रधानमंत्री शक्तियों पर विचार करने के कम
उदाहरण के लिए की जरूरत है
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
अब तुम wo के भीतरी पाश ठीक कर सकते हैं अधिक गति प्राप्त करने के लिए आरके थोड़ा अलग है, और आप primes_less_than(N) फ़ंक्शन को सटीक बना सकते हैं।
संपादित करें:
हाल ही में एक वोट दें के कारण मैं इस पर दोबारा जाने, देखने का तरीका अन्य सूचीबद्ध एल्गोरिदम के साथ गति तुलना चला गया decideded।
Joes: 1.85s अंक: 3.26s खान: 0.33s
यहाँ एक लॉग है
10k पुनरावृत्तियों, जो Beibers और मार्क फिरौती तरीकों के खिलाफ के साथ सीमा 1-160 के लिए समय इस प्रकार हैं
01: अप करने के लिए 300.
कोड अपने परीक्षण यहां पाया जा सकता के लिए परिणामों के साथ -log ग्राफ
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)
btw - जवाब 10,581,480 है? मेरा मानना है कि यह विशेष समस्या का सही उत्तर है :) – warren
@warren - मैं आपके उत्तर से बाहर निकल गया था, क्योंकि थोड़ी देर के लिए मैंने सोचा था कि आप सही थे (केवल इस सवाल को मिला), और एलसीएम कैलक्यूलेटर में मैंने लिखा था हास्केल एक जंगली अलग जवाब दे रहा था, और 10581480 [1..20] तक विभाजित होना प्रतीत होता था। मैंने कहीं गलती की होनी चाहिए क्योंकि आपका उत्तर 11 या 16 तक समान रूप से विभाजित नहीं है। सही उत्तर 232792560 है। –
@ मैट एलन - अच्छी कॉल, सुनिश्चित नहीं है कि मैं अपने उत्तर में 11 कैसे चूक गया :) – warren