我现在正在进行Euler项目。我昨天开始用Python解决一个复杂的问题。在
我在第五题,它要求我找出最小的正数,它可以被1到20的所有数整除。在
我知道如何用纸和铅笔来解决这个问题,我已经用编程解决了,但是为了优化它,我在Euler项目的论坛上交叉了这个解决方案。在
它看起来很优雅,和我的相比,它相当快,可笑的快,因为它需要大约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的用户发布的
该代码正在计算从}(或您使用的任何一个
1
到{range
)的最小公倍数。在它从}的因子,如果不是(即当
1
开始,然后对该范围内的每个数字k
检查k
是否是{i % k > 0
时),它将该数作为因子相加。在但是,做}时,用}就足够了,所以内循环会找到最小的数}就有{}作为因子。在
i *= k
不会产生最小的公共倍数,因为例如当你有i = 2
和{i
乘以{j
,这样{最后,在这个范围内的每个数
k
都是i % k == 0
,为了这样做,我们总是加上最小因子,从而计算出最小公倍数。在也许准确地展示价值观的变化有助于理解这一过程:
您可以立即注意到以下几点:
1
从不执行任何操作,range(1, 21)
可以安全地更改为range(2, 21)
k
都是一个质数,内部循环在j=k
时结束,并以i *= k
结束。这是意料之中的,因为当k
是一个素数时,它没有因子,所以没有一个更小的数j
的选择,这会使i
成为{i
乘以一个数j < k
,因此{i
中。在Bakuriu通过解释lassevk的“阶乘”算法回答了您的问题。然而,有一种更简单的方法来实现这一点,对于更大的输入来说速度更快。在
让
num
是序列中最高的数字。例如num = 20
。在只需将从2到
num
的所有数字相乘,并在每一步除以当前乘数和当前乘积的GCD(最大公分母)。在在这段代码中,我将产品初始化为
num
,只是为了使循环看起来更好一些。在输出
^{pr2}$对于}时,它大约快14倍。在
num
的小值,该算法与lassevk算法的时间差不多。但当num = 1000
时,它大约快4倍,当{正如Bakuriu在评论中提到的,
fractions
模块提供了一个gcd
函数。这使得代码稍微缩短了一些,但它并没有在我的测试中提供加速。在下面是一些python2/python3代码,它们对我的算法的2个变体进行实际的
timeit
测试。在Python2.6.6上,使用fractions.gcd
的版本要慢10%左右,但在Python3.6上,它可以慢5到10倍!这两个测试都是在运行Debian衍生Linux的旧2GHz机器上进行的。在Python2.6输出
Python3.6输出
相关问题 更多 >
编程相关推荐