logo标签列表

在Python中解决欧拉计划第5题 - 我该如何优化我的解决方案？

python
10

我最近在用Python解决项目欧拉（Project Euler）问题。我对Python还比较陌生，作为一个程序员也还是新手。

无论如何，我在编写第5个问题的解决方案时遇到了一个与速度相关的问题。这个问题是：

"2520是最小的能够被1~10中的每个数整除的数，没有余数。什么是能够被1~20中的数整除的最小正整数？"

我查阅了一些资料，但并没有找到针对Python特别的问题解答。有一些已经完成的脚本，但如果可能的话，我想要避免完全查看他人的代码，而是想要改进自己的代码。

我编写的代码可以成功地运行在2520和1到10的范围内的例子上，并且应该可以直接修改以适用于这个问题。然而，在运行它时，我没有得到答案。很可能是因为它是一个非常大的数字，而代码不够快。打印正在检查的当前数字似乎支持这一点，数字达到几百万却没有得到答案。

目前的代码实现如下：

rangemax = 20
def div_check(n):
    for i in xrange(11,rangemax+1):
        if n % i == 0:
            continue
        else:
            return False
    return True

if __name__ == '__main__':
   num = 2
   while not div_check(num):
       print num
       num += 2
   print num

我已经进行了一些改变，我认为这些改变应该会提高速度。首先，要使一个数字能够被1到20之间的所有数字整除，它必须是偶数，因为只有偶数可以被2整除。因此，我可以将递增量从1改为2。此外，虽然我没有想到这个点子，但我发现有人指出，一个可以被11到20整除的数字也可以被1到10整除。（我还没有检查过，但这似乎是合理的）

然而，代码仍然不够快。有哪些优化措施，无论是程序方面还是数学方面，可以让这个代码运行得更快呢？

提前感谢任何能够帮助我的人。

6
与代码无关，但是根据您注意到数字必须是2的倍数的逻辑，您还可以得出结论它必须是3、4、……、10的倍数，因此必须是所有这些数字的最小公倍数的倍数，即2520。 - David Z
1
它的范围很广，可以是两者兼备，但我认为你可以做出的最有益的优化将是数学上的而不是程序上的。尽管如此，Stack Overflow对于什么构成编程相关问题的标准并不特别严格，所以我想这里没问题。 - David Z
10
例如，对于这个问题，使用数学知识很容易进行质因数分解，并找出所有这些数字的最小公倍数为232792560 = 2*2*2*2*3*3*5*7*11*13*17*19。但是，要看问题类型来确定手动数学是否足够有效，或者一个简单的程序能否更快地（或更高效地）解决它。 - poke
2
@poke：这很简单。[Giltheryn剧透！！！你已经被警告了]请看这里：https://dev59.com/znVC5IYBdhLWcg3w51ry#147539。 - jfs
@J.F.Sebastian：但是公平地说，将2*2*2*2*3*3*5*7*11*13*17*19相乘只需要0.1微秒 :-P - David Z
显示剩余7条评论
21个回答
25

根据Michael Mior和poke的建议，我写了一个解决方案。我尝试使用了一些技巧使它更快。

由于我们需要测试相对较短的数字列表，因此我们可以预先构建数字列表，而不是反复调用xrange()或range()。

同时，虽然把数字[1, 2, 3, ..., 20]放入列表中也可以工作，但我们可以想一想并取出一些数字：

只需取出1即可。每个整数都能够被1整除。

如果保留20，则无需保留2。任何被20整除的整数也能被2整除（但反过来则未必成立）。所以我们保留20并取出2、4和5。为保留19作为质数，我们还要保留18，但现在可以取出3和6。如果您重复此过程，最终会得到一个更短的数字列表。

我们从20开始，按20步长移动数字，就像Michael Mior建议的那样。我们在all()内部使用生成器表达式，就像poke建议的那样。

我使用了xrange()的for循环而不是while循环；我认为这样略微更快。

结果：

check_list = [11, 13, 14, 16, 17, 18, 19, 20]

def find_solution(step):
    for num in xrange(step, 999999999, step):
        if all(num % n == 0 for n in check_list):
            return num
    return None

if __name__ == '__main__':
    solution = find_solution(20)
    if solution is None:
        print "No answer found"
    else:
        print "found an answer:", solution

在我的电脑上，这个程序可以在不到九秒钟的时间内找到一个答案。

编辑： 如果我们采纳David Zaslavsky的建议，我们可以从2520开始循环，并以2520为步长进行迭代。如果我这样做，在我的电脑上只需要大约十分之一的时间就可以得到正确的答案。

我修改了find_solution()函数，使其接受一个参数。尝试调用find_solution(2520)。

我想到我们可以编写Python代码来生成一系列数字 [2, 3, 4, 5, ..., N]，然后循环遍历它并取出所有不需要的数字。然后，我们可以将所有取出的数字相乘以获得我们的起始值和步长值。这距离最优解只有几个步骤之遥，即找到最小的质因数集合并将它们全部相乘。 - steveha
哦，你不能只是简单地将所有提取出来的数字相乘；因为该列表包括2、4、6、8、10等数字。最终答案太大了，因为它有比应该有的更多的2的因子等等。这是一个常见的倍数，但不是最小公倍数。 - steveha
非常好，很有帮助，谢谢。实现这些逻辑的大部分，可以在几秒钟内找到解决方案，而不是之前的10分钟。 - George Osterweil
在完全实现后，代码在不到一秒钟的时间内完成。我没有测量确切的运行时间，但它足够快。 - George Osterweil
我觉得这段代码返回的答案是“20”，而不是实际的解决方案，我哪里出错了还是其他人得到了类似的答案？ - KRS-fun
我只是复制了代码，将其保存为Python脚本并运行它。我没有得到20作为答案，而是得到了正确的答案。 - steveha
8

我的第一个答案加速了原问题的计算。

这里还有另一个解决方法：只需找到每个数字的所有质因数，然后将它们相乘即可直接得出答案。换句话说，这自动化了poke在评论中推荐的过程。

它可以在几分之一秒内完成。我认为没有比这更快的方法了。

我在Google上搜索了“Python查找质因数”，找到了这个：

http://www.stealthcopter.com/blog/2009/11/python-factors-of-a-number/

从那里我找到了一个链接到 factor.py（由Mike Hansen编写）的页面，其中包含一些有用的函数：

https://gist.github.com/weakish/986782#file-factor-py

他的函数并没有完全符合我的要求，所以我编写了一个新的函数，但是使用了他的 pull_prime_factors() 来完成繁重的工作。结果是 find_prime_factors() 函数，它返回一个元组列表：一个质数和一个计数。例如，find_prime_factors(400) 返回 [(2,4), (5,2)]，因为 400 的质因数是：(2*2*2*2)*(5*5)。
然后我使用一个简单的 defaultdict() 来跟踪每个质因数已经出现的次数。
最后，循环将所有内容相乘。
from collections import defaultdict
from factor import pull_off_factors

pf = defaultdict(int)

_primes = [2,3,5,7,11,13,17,19,23,29]
def find_prime_factors(n):
    lst = []
    for p in _primes:
        n = pull_off_factors(n, p, lst)
    return lst

def find_solution(low, high):
    for num in xrange(low, high+1):
        lst = find_prime_factors(num)
        for n, count in lst:
            pf[n] = max(pf[n], count)

    print "prime factors:", pf
    solution = 1
    for n, count in pf.items():
        solution *= n**count

    return solution

if __name__ == '__main__':
    solution = find_solution(1, 20)
    print "answer:", solution

编辑：哇，我刚看了@J.F. Sebastian回答相关问题的答案。他的答案本质上与上面的代码执行相同的操作，只是更加简单优雅。而且实际上比上面的代码更快。

三个或更多数字的最小公倍数

我会保留上面的内容，因为我认为这些函数可能在欧拉计划中有其他用途。但这里是J.F. Sebastian的解决方案：

def gcd(a, b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Return lowest common multiple."""
    return a * b // gcd(a, b)

def lcmm(*args):
    """Return lcm of args."""   
    return reduce(lcm, args)

def lcm_seq(seq):
    """Return lcm of sequence."""
    return reduce(lcm, seq)

solution = lcm_seq(xrange(1,21))
print "lcm_seq():", solution

我添加了lcm_seq()，但你也可以调用：

lcmm(*range(1, 21))
factor.py的链接已经失效了。如果您还有它，能否在这里发布一下？ - Keatinge
@Keatinge 当我尝试使用以下链接时，它对我有效：https://gist.github.com/weakish/986782#file-factor-py。指向该要点的博客文章似乎已经失效了。 - steveha
6

由于你的答案必须是20的倍数，因此可以从20开始，每次增加20而不是增加2。一般情况下，可以从rangemax开始，每次增加rangemax。这将使得调用div_check的次数减少一个数量级。

4

将数字分解为质因数。

小于20的所有质数为：

2,3,5,7,11,13,17,19

所以，可以被这些数字整除的最小值为：
2*3*5*7*11*13*17*19

复合材料：

4,6,8,9,10,12,14,15,16,18,20 = 2^2, 2*3, 2^3, 3^2, 2*5, 2^2*3, 2*7, 3*5, 2*3^2, 2^2*5

从左到右看需要哪些因素：

  • 使用2的3次方可以得到 4, 8, 和 16
  • 使用3可以得到 9
  • 质因数分解：2的4次方 * 3的2次方 * 5 * 7 * 11 * 13 * 17 * 19 = 232792560
这正是欧拉计划旨在激发的思维方式。前几个问题只需要数学思维，而不需要编程。 - Pete Kirkham
这很有道理。我将这个概念应用到我的解决方案中，Java的响应时间从约7秒降至约2毫秒。我不明白为什么这不是被接受的答案。 - Dorado
2
我用以下步骤在0.066毫秒内（仅通过74次循环）找到了解决方案：
从1开始，寻找下一个数字的最小倍数。将前一个数字的最小倍数加上自身（smallest_multiple = smallest_multiple + prev_prod），直到next_number_up % smallest_multiple == 0。此时，smallest_multiple是下一个数字的正确最小倍数。然后增加next_number_up并重复此过程，直到达到所需的最小倍数（在本例中为20次）。我相信这大约需要n*log(n)时间来找到解决方案（尽管，考虑到数字的工作方式，通常似乎比那快得多）。
例如：
1是1的最小倍数
查找2的最小倍数
检查以前的最小倍数是否有效1/2 = .5，因此不行
以前的最小倍数+以前的最小倍数==2。
检查2是否可被2整除-是，因此2是2的最小倍数
查找3的最小倍数
检查以前的最小倍数是否有效2/3 = .667，因此不行
以前的最小倍数+以前的最小倍数==4
检查3是否可被4整除-不
4+以前的最小倍数==6
检查6是否可被3整除-是，因此6是3的最小倍数
查找4的最小倍数
检查以前的最小倍数是否有效6/4 = 1.5，因此不行
以前的最小倍数+以前的最小倍数==12
检查4是否可被12整除-是，因此12是4的最小倍数
重复直到20..
以下是用Ruby实现此方法的代码：
def smallestMultiple(top)
    prod = 1
    counter = 0
    top.times do
        counter += 1
        prevprod = prod
        while prod % counter != 0
            prod = prod + prevprod
        end
    end
    return prod
end
1
这里我也使用了质因数分解的方法。
#!/usr/bin/env python
import math
def is_prime(num):
    if num > 1:
        if num == 2:
            return True
        if num%2 == 0:
            return False
        for i in range(3, int(math.sqrt(num))+1, 2):
            if num%i == 0:
                return False
        return True
    return False

def lcm(number):
    prime = []
    lcm_value = 1
    for i in range(2,number+1):
        if is_prime(i):
            prime.append(i)
    final_value = []
    for i in prime:
        x = 1
        while i**x < number:
            x = x + 1
        final_value.append(i**(x-1))
    for j in final_value:
        lcm_value = j * lcm_value
    return lcm_value

if __name__ == '__main__':
    print lcm(20)

经过检查所花费的时间，结果还不错。

root@l-g6z6152:~/learn/project_euler# time python lcm.py

232792560

real    0m0.019s
user    0m0.008s
sys 0m0.004s
1
这个解决方案对我来说运行得非常快（导入numpy）。
t0 = time.time()
import numpy

ints = numpy.array(range(1,21))
primes = [2,3,5,7,11,13,17,19] # under 20
facts = []
for p in primes:
    counter = 0
    nums = ints
    while any(nums % p == 0):
        nums = nums / float(p)
        counter += 1
    facts.append(counter)

facts = numpy.array(facts)
mults = primes**facts
ans = 1
for m in mults:
    ans = m * ans

t1 =time.time()
perf = t1 - t0
print "Problem 5\nAnswer:",ans, "runtime:", perf, "seconds"

"""Problem 5
Answer: 232792560 runtime: 0.00505399703979 seconds"""
1

列表推导式比for循环更快。

要检查一个数字，可以像这样做：

def get_divs(n):
    divs = [x for x in range(1,20) if n % x == 0]
    return divs

您可以检查divs数组的长度，以查看所有数字是否出现。
1
然后你也可以简单地执行 return all( n % x == 0 for x in range(1,21) ) - 注意上限范围为 21，以包括检查中的 20。 - poke
我还没有涉及到列表推导式，但是很容易找到相关信息。我会去查一下的，谢谢。 - George Osterweil
Glitheryn，khil的解决方案是列表推导式解决方案，它生成一个列表。Poke的解决方案是“生成器表达式”解决方案，类似于listcomp但不构建整个列表；它一次产生一个数字，这给出了速度优势。Listcomp必须构建一个列表；如果您不想要列表，而只是数字，则列表会被使用一次，然后再次拆开。通过genexp可以避免构建和拆除列表的开销。 - steveha
1
这里发布了两种不同类型的解决方案。一种使用gcd计算，另一种使用质因数分解。我将提出第三种类型，它基于质因数分解方法，但比质因数分解本身要快得多。它依赖于有关质数幂（某些整数指数下的质数）的一些简单观察结果。简而言之，事实证明，所有小于某个数字n的数字的最小公倍数等于n以下所有“最大质数幂”的乘积。
为了证明这一点，我们首先考虑x，即所有小于n的数字的最小公倍数，必须具有的属性，并用质数幂来表达它们。

  1. x 必须是小于 n 的所有质数幂的倍数。这很明显；假设 n = 20。 2，2 * 2，2 * 2 * 2 和 2 * 2 * 2 * 2 都小于 20，因此它们都必须能够整除 x。同样地，3 和 3 * 3 都小于 n，因此它们都必须能够整除 x。

  2. 如果某个数字 a 是质数幂 p ** e 的倍数，并且 p ** e 是小于 n 的最大的 p 的幂，则 a 也是所有更小的 p 的质数幂的倍数。这也很明显；如果 a == p * p * p，那么 a == (p * p) * p。

  3. 根据唯一分解定理，任何数字 m 都可以表示为小于 m 的质数幂的倍数。如果 m 小于 n，那么 m 可以表示为小于 n 的质数幂的倍数。

综上所述，后两个观察结果表明，任何一个是所有小于 n 的最大质数幂的倍数的数字 x 必须是所有小于 n 的数字的公共倍数。根据（2），如果 x 是所有小于 n 的最大质数幂的倍数，则它也是所有小于 n 的质数幂的倍数。因此，根据（3），它还是所有小于 n 的其他数字的倍数，因为它们都可以表示为小于 n 的质数幂的倍数。

最后，根据（1），我们可以证明 x 也是所有小于 n 的数字的最小公倍数，因为小于 x 的任何数字都不能是所有小于 n 的最大质数幂的倍数，因此不能满足（1）。

总之，这一切的结果是，我们不需要分解任何东西。我们只需生成小于 n! 的质数即可。

如果使用优化良好的埃拉托斯特尼筛法，可以在一百万以下的n上非常快速地完成。然后，您只需要找到每个质数下小于n的最大质数幂，并将它们相乘即可。

prime_powers = [get_max_prime_power(p, n) for p in sieve(n)]
result = reduce(operator.mul, prime_powers)

我将把编写get_max_prime_power留作练习。结合上述方法，快速版本可以在我的机器上在3秒内生成所有小于200000的数字的最小公倍数。

结果是一个86871位数的数字！

@steveha，我认为你的质因数分解方法是正确的；请参见上文中的另一种优化方法，它（在我的机器上）比这里任何基于“gcd”的代码都要快得多，至少对于大值来说是如此。 - senderle
1
我写了一个解决 euler5 的方案，其中包含以下 html 标记：

。
  • Is orders of magnitude faster than most of the solutions here when n=20 (though not all respondents report their time) because it uses no imports (other than to measure time for this answer) and only basic data structures in python.

  • Scales much better than most other solutions. It will give the answer for n=20 in 6e-05 seconds, or for n=100 in 1 millisec, faster than most of the responses for n=20 listed here.

    import time
a=time.clock() # set timer

j=1
factorlist=[]
mydict={}
# change second number to desired number +1 if the question were changed.
for i in range(2,21,1):
    numberfactors=[]
    num=i
    j=2
# build a list of the prime factors
    for j in range(j,num+1,1):
        counter=0
        if i%j==0:
            while i%j==0:
                counter+=1
                numberfactors.append(j)
                i=i/j
# add a list of factors to a dictionary, with each prime factor as a key
                if j not in mydict:
                    mydict[j] = counter
# now, if a factor is already present n times, including n times the factor
# won't increase the LCM. So replace the dictionary key with the max number of
# unique factors if and only if the number of times it appears is greater than
# the number of times it has already appeared.
# for example, the prime factors of 8 are 2,2, and 2. This would be replaced 
# in the dictionary once 16 were found (prime factors 2,2,2, and 2).
            elif mydict[j] < counter:
                mydict[j]=counter

total=1
for key, value in mydict.iteritems():
    key=int(key)
    value=int(value)
    total=total*(key**value)

b=time.clock()
elapsed_time=b-a
print total, "calculated in", elapsed_time, "seconds"

    returns:

    232792560 calculated in 6e-05 seconds

# does not rely on heuristics unknown to all users, for instance the idea that 
# we only need to include numbers above 10, etc.


# For all numbers evenly divisible by 1 through 100:
69720375229712477164533808935312303556800 calculated in 0.001335 seconds
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接