瞭解通過歐拉項目在Python

Question

目前我要去解決歐拉項目。我已經開始使用JavaScript，並且我昨天已經切換到了Python，因爲我陷入了一個似乎很難用Javascript解決的問題，但是很容易用Python解決，所以我決定從第一個問題開始蟒蛇。

我在這問我找到最小的正數，它是所有從1數的整除到20

我知道如何與紙筆解決它，我的問題5我已經使用編程解決了，但爲了優化它，我在歐拉項目的論壇中跨越了這個解決方案。

看來優雅和快速相比，我的是相當快的，可笑的，因爲它需要約2秒鐘來解決同樣的問題，對數字1到1000，在那裏我的需要幾分鐘的時間。

我試着去了解它，但我仍然有困難，把握它到底在做什麼。那就是：

i = 1 
for k in (range(1, 21)): 
    if i % k > 0: 
     for j in range(1, 21): 
      if (i*j) % k == 0: 
       i *= j 
       break 
print i 

它最初發布名爲lassevk

Answer 1

該代碼是計算數字的最小公倍數從1到20（或任何其他range您使用的用戶）。

它從1開始，然後在它會檢查是否k是i一個因素在該範圍的每個數字k，如果沒有（即，當i % k > 0）它增加了該號碼的一個因素。

但是做i *= k不會產生至少公倍數，例如因爲當你有i = 2和k = 6這足以乘以3i有i % 6 == 0，使內環發現數最少j這樣i*j有k作爲一個因素。

最終在範圍內的每個數k使得i % k == 0和我們總是添加最小因素，以做到這一點，因此，我們計算出的至少公倍數。

---

也許顯示準確的數值如何變化可幫助瞭解過程：

i = 1 
k = 1 
i % k == 0 -> next loop 

i = 1 
k = 2 
i % k == 1 > 0 
    j = 1 
    if (i*j) % k == 1 -> next inner loop 
    j = 2 
    if (i*j) % k == 0 
     i *= j 
i = 2 
k = 3 
i % k == 2 > 0 
    j = 1 
    if (i*j) % k == 2 -> next inner loop 
    j = 2 
    if (i*j) % k == 4 % 3 == 1 -> next inner loop 
    j = 3 
    if (i*j) % k == 6 % 3 == 0 
     i *= j 
i = 6 
k = 4 
i % k == 2 > 0 
    j = 1 
    if (i*j) % k == 6 % k == 2 -> next inner loop 
    j = 2 
    if (i*j) % k == 12 % k == 0 
     i *= j 
i = 12 
k = 5 
i % k == 2 > 0 
    j = 1 
    if (i*j) % k == 12 % k == 2 -> next inner loop 
    j = 2 
    if (i*j) % k == 24 % k == 4 -> next inner loop 
    j = 3 
    if (i*j) % k == 36 % k == 1 -> next inner loop 
    j = 4 
    if (i*j) % k == 48 % k == 3 -> next inner loop 
    j = 5 
    if (i*j) % k == 60 %k == 0 
     i *= j 
i = 60 
... 

您可以立即看到幾件事情：

• 的range(1, 21)可以安全，因爲改爲range(2, 21)在1從來沒有做任何事情
• 每次k是一個素數的內循環結束時j=k並且將在i *= k結束。這是預期的，因爲當k是一個主要因素時，它沒有任何因素，所以沒有選擇較小的數字j，這將使ik的倍數。
• 在其他情況下，編號i乘以j < k的數字，以便k的所有因子現在位於i中。

Answer 2

Bakuriu通過解釋lassevk的「階乘」算法來回答你的問題。但是，有一種更簡單的方法可以做到這一點，對於較大的輸入速度要快得多。

讓num爲序列中最高的數字。所以對於你的例子num = 20。

簡單地將所有從2到num的數字相乘，然後在每一步除以當前乘數和當前乘積的GCD（最大公分母）。

在此代碼中，我將產品初始化爲num，只是爲了使循環看起來更好。

num = 20 

p = num 
for i in range(2, num): 
    # Compute GCD(p, i) using Euclid's algorithm 
    # When the loop ends, a is the GCD 
    a, b = p, i 
    while b: 
     a, b = b, a % b 
    p *= i // a 

print(p) 

輸出

232792560 

對於num這個算法小的值大約需要同時lassevk的算法。但是，當num = 1000約快4倍，而當num = 2000約快14倍。

---

如Bakuriu評價提到，所述fractions模塊提供gcd功能。這使得代碼稍微短一點，但是在我的測試中並沒有提供加速。

from fractions import gcd 

num = 20 

p = num 
for i in range(2, num): 
    p *= i // gcd(p, i) 

print(p) 

---

下面是一些Python的2/3的Python代碼，做實際timeit測試，比較我的算法2度的變化。在Python 2.6.6中，使用fractions.gcd的版本慢了大約10％，但是在Python 3.6中，它可能慢5到10倍！這兩項測試都是在運行Debian衍生Linux的老式2GHz機器上進行的。

''' Test the speed of calculating the Least Common Multiple 
    via an inline implementation of Euclid's GCD algorithm 
    vs the gcd function from the fractions module 

    See http://stackoverflow.com/q/38074440/4014959 

    Written by PM 2Ring 2016.06.28 
''' 

from timeit import Timer 
from fractions import gcd 

def lcm0(num): 
    p = num 
    for i in range(2, num): 
     a, b = p, i 
     while b: 
      a, b = b, a % b 
     p *= i // a 
    return p 

def lcm1(num, gcd=gcd): 
    p = num 
    for i in range(2, num): 
     p *= i // gcd(p, i) 
    return p 

funcs = (lcm0, lcm1) 

def time_test(loops, reps): 
    ''' Print timing stats for all the functions ''' 
    for func in funcs: 
     fname = func.__name__ 
     setup = 'from __main__ import num,' + fname 
     cmd = fname + '(num)' 
     t = Timer(cmd, setup) 
     r = t.repeat(reps, loops) 
     r.sort() 
     print('{0}: {1}'.format(fname, r)) 

num = 5 
loops = 8192 
reps = 5 
for _ in range(10): 
    print('\nnum={0}, loops={1}'.format(num, loops)) 
    time_test(loops, reps) 
    num *= 2 
    loops //= 2 

的Python 2.6輸出

num=5, loops=8192 
lcm0: [0.055649995803833008, 0.057304859161376953, 0.057752132415771484, 0.060063838958740234, 0.064462900161743164] 
lcm1: [0.067559003829956055, 0.068048954010009766, 0.068253040313720703, 0.069074153900146484, 0.084647893905639648] 

num=10, loops=4096 
lcm0: [0.058645963668823242, 0.059965133666992188, 0.060016870498657227, 0.060331821441650391, 0.067235946655273438] 
lcm1: [0.072937965393066406, 0.074002981185913086, 0.074270963668823242, 0.074965953826904297, 0.080986976623535156] 

num=20, loops=2048 
lcm0: [0.063373088836669922, 0.063961029052734375, 0.064354896545410156, 0.071543216705322266, 0.10234284400939941] 
lcm1: [0.079973936080932617, 0.080717802047729492, 0.082272052764892578, 0.086506843566894531, 0.11265397071838379] 

num=40, loops=1024 
lcm0: [0.077324151992797852, 0.077867984771728516, 0.07857513427734375, 0.087296962738037109, 0.10289192199707031] 
lcm1: [0.095077037811279297, 0.095172882080078125, 0.095523834228515625, 0.095964193344116211, 0.10543298721313477] 

num=80, loops=512 
lcm0: [0.09699702262878418, 0.097161054611206055, 0.09722590446472168, 0.099267005920410156, 0.10546517372131348] 
lcm1: [0.1151740550994873, 0.11548399925231934, 0.11627888679504395, 0.11672496795654297, 0.12607502937316895] 

num=160, loops=256 
lcm0: [0.10686612129211426, 0.10825586318969727, 0.10832309722900391, 0.11523914337158203, 0.11636996269226074] 
lcm1: [0.12528896331787109, 0.12630200386047363, 0.12688708305358887, 0.12690496444702148, 0.13400888442993164] 

num=320, loops=128 
lcm0: [0.12498903274536133, 0.12538790702819824, 0.12554287910461426, 0.12600493431091309, 0.13396120071411133] 
lcm1: [0.14431190490722656, 0.14435195922851562, 0.15340209007263184, 0.15408897399902344, 0.159912109375] 

num=640, loops=64 
lcm0: [0.15442395210266113, 0.15479183197021484, 0.15657520294189453, 0.16451501846313477, 0.16749906539916992] 
lcm1: [0.17400288581848145, 0.17454099655151367, 0.18450593948364258, 0.18503093719482422, 0.19588208198547363] 

num=1280, loops=32 
lcm0: [0.21137905120849609, 0.21206808090209961, 0.21211409568786621, 0.21935296058654785, 0.22051215171813965] 
lcm1: [0.23439598083496094, 0.23578977584838867, 0.23717594146728516, 0.24761080741882324, 0.2488548755645752] 

num=2560, loops=16 
lcm0: [0.34246706962585449, 0.34283804893493652, 0.35072207450866699, 0.35794901847839355, 0.38117814064025879] 
lcm1: [0.3587038516998291, 0.36004209518432617, 0.36267900466918945, 0.36284589767456055, 0.37285304069519043] 

的Python 3.6輸出

num=5, loops=8192 
lcm0: [0.0527388129994506, 0.05321520800134749, 0.05394392299785977, 0.0540059859995381, 0.06133090399816865] 
lcm1: [0.45663526299904333, 0.4585357750002004, 0.45960231899880455, 0.4768777699973725, 0.48710195899911923] 

num=10, loops=4096 
lcm0: [0.05494695199740818, 0.057305197002278874, 0.058495635999861406, 0.07243769099659403, 0.07494244600093225] 
lcm1: [0.5807856120009092, 0.5809524680007598, 0.5971023489983054, 0.6006399979996786, 0.6021203519994742] 

num=20, loops=2048 
lcm0: [0.06225249999988591, 0.06330173400056083, 0.06348088900267612, 0.0639248730003601, 0.07240132099832408] 
lcm1: [0.6462642230035271, 0.6486189150018618, 0.6605903060008131, 0.6669839690002846, 0.7464891349991376] 

num=40, loops=1024 
lcm0: [0.06812337999872398, 0.06989315700047882, 0.07142737200047122, 0.07237963000079617, 0.07640906400047243] 
lcm1: [0.6938937240011, 0.7021358079982747, 0.7238045579979371, 0.7265497620028327, 0.7266306150013406] 

num=80, loops=512 
lcm0: [0.07672808099960093, 0.07784233300117194, 0.07959756200216361, 0.08742279999933089, 0.09116945599816972] 
lcm1: [0.7249167879999732, 0.7272519250000187, 0.7329213439988962, 0.7570086350024212, 0.75942590500199] 

num=160, loops=256 
lcm0: [0.08417846500015003, 0.08528995099914027, 0.0856771619983192, 0.08571110499906354, 0.09348897000018042] 
lcm1: [0.7382230039984279, 0.7425414600002114, 0.7439042109981528, 0.7505959240006632, 0.756812355000875] 

num=320, loops=128 
lcm0: [0.10246147399811889, 0.10322481399998651, 0.10324400399986189, 0.10347093499876792, 0.11325025699989055] 
lcm1: [0.7649764790003246, 0.7903363080004056, 0.7931463940003596, 0.8012050910001562, 0.8284494129984523] 

num=640, loops=64 
lcm0: [0.13264304200129118, 0.13345745100014028, 0.13389246199949412, 0.14023518899921328, 0.15422578799916664] 
lcm1: [0.8085992009982874, 0.8125102049998532, 0.8179558970005019, 0.8299506059993291, 0.9141929620018345] 

num=1280, loops=32 
lcm0: [0.19097876199884922, 0.19147844200051622, 0.19308, 0.19317538399991463, 0.20103917100277613] 
lcm1: [0.8671656119986437, 0.8713741569990816, 0.8904907689975516, 0.9020749549999891, 0.9131527989993629] 

num=2560, loops=16 
lcm0: [0.3099351109995041, 0.31015214799845126, 0.3101941059976525, 0.32628724800088094, 0.3492128660000162] 
lcm1: [0.9883516860027157, 0.988955139000609, 0.9965159560015309, 1.0160803129983833, 1.0170008439999947]